HDU-2586-How far away ？(最近公共祖先)

How far away ？

题意

• 找出两点的距离

思路

• 找出两点的公共祖先，根节点到两点的距离之和减去两倍根节点到公共最近祖先的距离

#include<bits/stdc++.h>
using namespace std;
const int M=80000+10;
vector<pair<int,int> >vep[M];//存放两点关系
vector<pair<int,int> >p[M];//存放询问
int root[M];
int dis[M];
int vis[M];
int ans[M];
int n,m;
int x,y,w;
void init(int n)
{
    for(int i=0;i<=n;i++)
    {
        root[i]=i;
        vep[i].clear( );
        p[i].clear( );
        dis[i]=vis[i]=ans[i]=0;
    }
}
int find(int x)
{
    if(x==root[x])
    {
        return x;
    }
    else
    {
        return find(root[x]);//返回上一层
    }
}
void ouin(int x,int y)
{
    int a=find(x);
    int b=find(y);
    if(a!=b)
    {
        root[b]=a;//子节点合并成父节点
    }
}
void tarjan(int x,int d)
{
    vis[x]=1;
    dis[x]=d;
    for(int i=0;i<vep[x].size( );i++)
    {
        int u=vep[x][i].first;
        int w=vep[x][i].second;
        if(vis[u])
        {
            continue;
        }
        tarjan(u,w+dis[x]);
        ouin(x,u);//合并父子节点
    }
    for(int i=0;i<p[x].size( );i++)
    {
        int w=p[x][i].first;
        int mark=p[x][i].second;
        if(vis[w])
        {
            //cout<<find(w)<<endl;
            ans[mark]=dis[w]+dis[x]-2*(dis[find(w)]);
        }
    }
}
int main( )
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        
        scanf("%d%d",&n,&m);
        init(n);
        for(int i=1;i<n;i++)
        {
            scanf("%d%d%d",&x,&y,&w);
            vep[x].push_back(make_pair(y,w));//记录两者距离
            vep[y].push_back(make_pair(x,w));
        }
        for(int i=1;i<=m;i++)
        {
            scanf("%d%d",&x,&y);
            p[x].push_back(make_pair(y,i));//记录两者序号
            p[y].push_back(make_pair(x,i));
        }
        tarjan(1,0);
        for(int i=1;i<=m;i++)
        {
            printf("%d\n",ans[i]);
        }
    }
    return 0;
}