hdu 2586 How far away ？ LCA離線算法

題目連結

題意：給出n個點，n-1條邊，保證每兩個點之間的路徑唯一，回答m個距離詢問。

LCA離線算法 tarjan模闆。

#include <iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<vector>
#define N 55000

using namespace std;

vector<int> h[N],w[N],q[N],num[N];
int ans[N],d[N],v[N],pre[N],n,m;

void init()
{
    for(int i=1;i<=n;i++)
    {
        h[i].clear();
        w[i].clear();
        q[i].clear();
        num[i].clear();
        pre[i]=i;
        d[i]=0;
        v[i]=0;
    }
}

int findset(int v)
{
    while(v!=pre[v])    v=pre[v];
    return v;
}

void unions(int u,int v)
{
    int t1=findset(u);
    int t2=findset(v);
    if(t1!=t2)  pre[t2]=t1;
}

void tarjan(int cur,int val)
{
    v[cur]=1;
    d[cur]=val;
    int len=h[cur].size();
    for(int i=0;i<len;i++)
    {
        int t=h[cur][i];
        if(v[t])    continue;
        tarjan(t,val+w[cur][i]);
        unions(cur,t);
    }
    len=q[cur].size();
    for(int i=0;i<len;i++)
    {
        int t=q[cur][i];
        if(!v[t])   continue;
        ans[num[cur][i]]=d[cur]+d[t]-2*d[findset(t)];
    }
}

int main()
{
    int T;
    cin>>T;
    while(T--)
    {
        cin>>n>>m;
        init();
        for(int i=1;i<n;i++)
        {
            int u,v,c;
            scanf("%d%d%d",&u,&v,&c);
            h[u].push_back(v);
            w[u].push_back(c);
            h[v].push_back(u);
            w[v].push_back(c);
        }
        for(int i=0;i<m;i++)
        {
            int u,v;
            scanf("%d%d",&u,&v);
            q[u].push_back(v);
            q[v].push_back(u);
            num[u].push_back(i);
            num[v].push_back(i);
        }
        tarjan(1,0);
        for(int i=0;i<m;i++)    cout<<ans[i]<<endl;
    }
}