AcWing 1171. 距离 Tarjan算法离线求LCA

题目

输入样例1：

2 2 
1 2 100 
1 2 
2 1

输出样例1： 

100
100

输入样例2：

3 2
1 2 10
3 1 15
1 2
3 2

输出样例2： 

10
25

LCA算法:

LCA(Least Common Ancestors)最近公共祖先

Tarjan 求 LCA 是一种离线的算法，也就是说它一遍求出所有需要求的点的 LCA，而不是需要求哪两个点再去求。

在深度优先遍历时，将所有点分成三大类：

[1]已经遍历过，且回溯过的点

[2]正在搜索的分支

[3]还未搜索到的点

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>

#define x first
#define y second

using namespace std;

typedef pair<int,int> PII;
const int N = 10010,M = 2*N;
int n,m;
int h[N],e[M],w[M],ne[M],idx;//邻接表
int dist[N];//每个点和1号点的距离
int p[N];//并查集
int res[M];//存储答案
int st[N];//存储每个节点的状态
vector<PII> query[N];//存储每组询问
// query[i][first][second] 
//first存查询距离i的另外一个点j，second存查询编号idx

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);
    }
}

//st[u]==2已经遍历并且回溯了
//st[u]==1正在遍历
void tarjan(int u)
{
    st[u]=1;//当前路径点标记为1
    // u这条路上的根节点的左下的点用并查集合并到根节点
    for(int i=h[u];~i;i=ne[i])
    {
        int j=e[i];
        if(!st[j])
        {
            tarjan(j);//往左下搜
            p[j]=u;//从左下回溯后把左下的点合并到根节点
        }
    }
    
    // 对于当前点u 搜索所有和u
    for(auto item:query[u])
    {
        int y=item.first,id=item.second;
        
        if(st[y]==2)//如果查询的这个点已经是左下的点
        {           //(已经搜索过且回溯过,标记为2)
            int anc=find(y);//y的根节点
            //y节点的p[y]已经回溯到公共祖先
            // x到y的距离 = d[x]+d[y] - 2*d[lca]
            res[id]=dist[u]+dist[y]-2*dist[anc];
            //第idx次查询的结果 res[idx]
        }
    }
    //点u已经搜索完且要回溯了 就把st[u]标记为2
    st[u]=2;
}
int main()
{
    cin>>n>>m;
    // 建图
    memset(h, -1, sizeof h);
    
    for(int i=0;i<n-1;i++)
    {
        int x,y,k;
        scanf("%d%d%d",&x,&y,&k);
        add(x,y,k);
        add(y,x,k);
    }
    
    // 存下询问
    for(int i=0;i<m;i++)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        if(x!=y)
        {
            query[x].push_back({y,i});
            query[y].push_back({x,i});
        }
    }
    
    for(int i=1;i<=n;i++)
        p[i]=i;
    
    dfs(1,-1);
    tarjan(1);
    
    for(int i=0;i<m;i++)
        printf("%d\n",res[i]);//把每次询问的答案输出
        
    return 0;
}