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

题目

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

思路

我们以以下样例来建一张图

首先我们假定点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;
}