bzoj 1787: [Ahoi2008]Meet 紧急集合

1787: [Ahoi2008]Meet 紧急集合

Description

Input

Output

Sample Input

6 4
1 2
2 3
2 4
4 5
5 6
4 5 6
6 3 1
2 4 4
6 6 6

Sample Output

5 2
2 5
4 1
6 0

HINT

题解：

n-1条边，很明显这是一棵树

那么题目就是求3个点的LCA

我们将3个点x,y,z分别求出x,y的LCA，设为a，x,z的为b，y,z的为c

则a,b,c 3个点中必有两个相等，答案就是另外一个（自已画画图就知道了）

那么再求3个点到它的距离就OK了。

#include<stdio.h>

#include<iostream>

#include<algorithm>

#include<string.h>

using namespace std;

int n,m,i,j,x,y,z,a,b,c,t,p[],r[],f[][];

int tot,head[],Next[],to[];

void add(int x,int y)

{

    tot++;

    to[tot]=y;

    Next[tot]=head[x];

    head[x]=tot;

}

void dfs(int x)

{

    int i;

    for(i=head[x];i!=-;i=Next[i])

        if(p[to[i]]==)

    {

        p[to[i]]=;

        r[to[i]]=r[x]+;

        f[to[i]][]=x;

        dfs(to[i]);

    }

}

int LCA(int a,int b)

{

    int i;

    if(r[a]<r[b]) swap(a,b);

    for(i=;i>=;i--)

        if(f[a][i]&&r[f[a][i]]>=r[b]) a=f[a][i];

    if(a==b) return a;

    for(i=;i>=;i--)

        if(f[a][i]&&f[b][i]&&f[a][i]!=f[b][i])

    {

        a=f[a][i];

        b=f[b][i];

    }

    return f[a][];

}

int dis(int x,int y)

{

    int a=LCA(x,y);

    return r[x]+r[y]-*r[a];

}

int main()

{

    scanf("%d%d",&n,&m);

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

        head[i]=-;

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

    {

        scanf("%d%d",&x,&y);

        add(x,y);

        add(y,x);

    }

    p[]=;

    r[]=;

    dfs();

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

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

     f[i][j]=f[f[i][j-]][j-];

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

    {

        scanf("%d%d%d",&x,&y,&z);

        a=LCA(x,y);

        b=LCA(x,z);

        c=LCA(y,z);

        if(a==b) t=c;else

        if(b==c) t=a;else

        t=b;

        printf("%d %d\n",t,dis(x,t)+dis(y,t)+dis(z,t));

    }

    return ;

}