题目
给出 n 个点的一棵树，多次询问两点之间的最短距离。
注意：
- 边是无向的。
- 所有节点的编号是 1,2,…,n。
输入格式
第一行为两个整数 n 和 m。n 表示点数，m 表示询问次数；
下来 n−1 行，每行三个整数 x,y,k，表示点 x 和点 y 之间存在一条边长度为 k；
再接下来 m 行，每行两个整数 x,y，表示询问点 x 到点 y 的最短距离。
树中结点编号从 1 到 n。
输出格式
共 m 行，对于每次询问，输出一行询问结果。
数据范围
2 ≤ n ≤ 10^4
1 ≤ m ≤ 2 × 10^4
0 < k ≤ 100
1 ≤ x , y ≤ n
思路
我们以以下样例来建一张图
样例：
10 0
1 2
1 3
2 4
2 5
3 6
3 7
4 8
4 9
8 10
首先我们假定点1为根节点，求出所有节点到点1的最短距离dist[ j ]。
我们可以假设点1为根节点，往下深度优先遍历每一个节点，只有当某一个节点的所有子节点都被便利之后才会更新其祖先节点，所以在这个点 a 的所有子节点没有遍历结束之前， a 的所有子节点的祖先都是节点 a 。易得，当求的两个点 x , y 都是属于点 a 的孙子结点的时候，x与y的距离为dist[ i ] + dist[ j ] - dist[ a ] * 2;
代码
#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> PII;
const int N = 20010, M = N * 2;
int n,m;
int h[N],e[M],w[M],ne[M],idx;
int res[N];
int dist[N];
int st[N];
int p[N];
vector<PII> query[N];
void add(int a,int b,int c)// 加点函数，使用邻接表储存该图
{
e[idx] = b,ne[idx] = h[a],w[idx] = c,h[a] = idx ++;
}
int find(int x)// 并查集板子
{
if(p[x] != x) p[x] = find(p[x]);
return p[x];
}
void dfs(int u,int fa)// 初始每个点到根节点的距离
{
for(int i = h[u]; ~i ; i = ne[i])
{
int j = e[i];
if(j == fa) continue;// 因为是无向边，所以会有一条边指向该点的父节点。
dist[j] = dist[u] + w[i];// 子节点距离根节点的距离为父节点加上父节点到该点的距离
dfs(j,u);//使用该点继续初始其他节点
}
}
void tarjan(int u)// 该题核心函数
{
st[u] = 1;
for(int i = h[u];~i; i = ne[i])// 每个点的祖先都是它的父节点
{
int j = e[i];
if(!st[j])
{
tarjan(j);// 以j为祖先节点，遍历所有j的所有子节点
p[j] = u;//将点j的所有子节点遍历完成之后，就更新点j的祖先节点
}
}
for(auto item : query[u])
{
int y = item.first,id = item.second;
if(st[y] == 2)// 如果点y已经完成遍历，则可以进行求距离操作
{
int anc = find(y);
res[id] = dist[u] + dist[y] - dist[anc] * 2;
}
}
st[u] = 2;//表示该点祖先节点已经更新，且所有子节点都已经完成遍历
}
int main()
{
cin >> n >> m;
memset(h,-1,sizeof(h));
for(int i = 1; i < n; i ++)//输入n-1条无向边
{
int a,b,c;
cin >> a >> b >> c;
add(a,b,c),add(b,a,c);
}
for(int i = 0; i < m; i ++)//输入m个询问
{
int a,b;
cin >> a >> b;
if(a == b) continue;
query[a].emplace_back(b,i);
query[b].emplace_back(a,i);
}
for(int i = 1; i <= n; i ++) p[i] = i;// 并查集初始化每个点所属的集合
dfs(1,-1);// 假设点1为该树的根节点
tarjan(1);
for(int i = 0; i < m; i ++) cout << res[i] << endl;
return 0;
}
