【算法】距离（最近公共祖先节点）

题目

给出 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;
}