HDU 2586 How far away？ Tarjan算法 并查集 LCA

#include<bits/stdc++.h>
using namespace std;
#define N 40000

typedef struct Edge
{
    int t,v;
    int next;
}edge;

edge E[N*2],e[N*2];
int cnt;
int head1[N],head2[N];//head1用于樹上節點的串連，head2用於詢問節點的串連
int dis[N],f[N],vis[N];//dis各點到根節點的距離，f為并查集
int ans[N][3];          //ans[0]和[1]記錄詢問點對，ans[3]記錄他們的公共祖先（LCA）
int n,m;
void addedge(int u,int v,int d,edge *a,int *head)
{
    a[cnt].t=v;
    a[cnt].v=d;
    a[cnt].next=head[u];
    head[u]=cnt++;

    a[cnt].t=u;
    a[cnt].v=d;
    a[cnt].next=head[v];
    head[v]=cnt++;
}

int findx(int a)//并查集
{
    if(a!=f[a])
        return f[a]=findx(f[a]);
    return a;
}

void getLCA(int p)//Tarjan算法求LCA
{
    vis[p]=1;
    f[p]=p;        //進入時初始化并查集

    for(int i=head2[p];i!=-1;i=e[i].next)//檢查詢問點對，是否發現已訪問
    {
        if(vis[e[i].t])
            ans[e[i].v][2]=findx(e[i].t);
    }

    for(int i=head1[p];i!=-1;i=E[i].next)//DFS搜索
    {
        if(!vis[E[i].t])
        {
            dis[E[i].t]=dis[p]+E[i].v;  //更新距離
            getLCA(E[i].t);
            f[E[i].t]=p;                //搜索過后更新子節點的并查集
        }
    }
}

int main()
{
    //freopen("a.txt","r",stdin);
    int T;
    scanf("%d",&T);
    while(T--)
    {
        cnt=0;
        memset(head1,-1,sizeof(head1));
        memset(head2,-1,sizeof(head2));
        scanf("%d%d",&n,&m);
        for(int i=1;i<=n-1;i++)
        {
            int a,b,v;
            scanf("%d%d%d",&a,&b,&v);
            addedge(a,b,v,E,head1);
        }
        cnt=0;
        for(int i=1;i<=m;i++)       //先全部記錄后離線處理
        {

            scanf("%d%d",&ans[i][0],&ans[i][1]);
            addedge(ans[i][0],ans[i][1],i,e,head2);
        }

        memset(vis,0,sizeof(vis));
        dis[1]=0;
        getLCA(1);

        for(int i=1;i<=m;i++)
            printf("%d\n",dis[ans[i][1]]+dis[ans[i][0]]-2*dis[ans[i][2]]);
    }       //最短距離 = 節點1的距離 + 節點2的距離 - 2*LCA的最短距離
}           //（這裡最短距離是指導根節點的距離）