bzoj1787

lca裸题，画画图看看就可以了，找出那个一次公共祖先，求距离

#include<iostream>

#include<set>

#include<cstring>

#include<algorithm>

#include<cmath>

#include<cstdio>

#include<vector>

using namespace std;

int n,m,u,v,a,b,c,ans,temp1;

int used[],dis[],dep[];

int acs[][];

vector<int>graph[];

void dfs(int u,int d)

{

    used[u]=;

    dep[u]=d;

    for(int i=;i<graph[u].size();i++)

    {

        int v=graph[u][i];

        if(!used[v])

        {

            acs[v][]=u;

            dfs(v,d+);

        }

    }

}

void get_acs()

{

    for(int j=;j<=;j++)

        for(int i=;i<=n;i++)

            if(acs[i][j-]<)

                acs[i][j]=-;

            else

                acs[i][j]=acs[acs[i][j-]][j-];

}

int lca(int x,int y)

{

    if(dep[x]<dep[y])

        swap(x,y);

    int d=dep[x]-dep[y];

    for(int k=;k>=;k--)

        if(acs[x][k]!=-&&(d&(<<k)))

            x=acs[x][k];

    if(x==y)

        return x;

    for(int k=;k>=;k--)

        if(acs[x][k]>&&acs[y][k]>&&acs[x][k]!=acs[y][k])

        {

            x=acs[x][k];

            y=acs[y][k];

        }

    return acs[x][];

}

inline int calc(int x,int y)

{

    int temp=lca(x,y);

    return abs(dep[x]-dep[temp])+abs(dep[y]-dep[temp]);

}

int main()

{

    cin>>n>>m;

    for(int i=;i<n;i++)

    {

        scanf("%d%d",&u,&v);

        graph[u].push_back(v);

        graph[v].push_back(u);

    }

    memset(acs,-,sizeof(acs));

    dfs(,);

    get_acs();

//    cout<<endl;

    for(int i=;i<=m;i++)

    {

        scanf("%d%d%d",&a,&b,&c);

        int x=lca(a,b);

        int y=lca(b,c);

        int z=lca(c,a);

        if(x==y)

            temp1=z;

        else

        if(y==z)

            temp1=x;

        else

        if(x==z)

            temp1=y;

        ans=calc(a,temp1)+calc(b,temp1)+calc(c,temp1);

        printf("%d %d\n",temp1,ans);

    }

    return ;

}