1787: [Ahoi2008]Meet 紧急集合

Time Limit: 20 Sec  Memory Limit: 162 MB
Submit: 2272  Solved: 1029
[Submit][Status][Discuss]

Description

Input

Output

Sample Input

Sample Output

HINT

Source

参考hzwer题解：

求最近公共祖先题目，dis函数求两点之间距离。

可以推导发现，三点间的lca必定有一对两两相等，所以确定哪两两相等后取另一个就是答案。

code如下：

#include<cstdio>

#include<cstring>

#include<iostream>

using namespace std;

bool vis[500100];

int q[500100],fa[500100][20],bin[20];

int n,m,u[1000100],v[1000100],deep[500100],first[1000100],nxt[1000100];

void make_bin()

{

    bin[0]=1;

    for(int i=1;i<=19;i++)

        bin[i]=bin[i-1]<<1;

}

void bfs()

{

    int head=0,tail=1;

    q[0]=1,vis[1]=true;

    while(head^tail){

        int now=q[head++];

        for(int i=1;i<=15;i++)

            if(bin[i]<=deep[now])

                fa[now][i]=fa[fa[now][i-1]][i-1];

            else break;

        for(int i=first[now];i;i=nxt[i])

            if(!vis[v[i]]){

                vis[v[i]]=true;

                fa[v[i]][0]=now;

                deep[v[i]]=deep[now]+1;

                q[tail++]=v[i];

            }

    }

}

int lca(int x,int y)

{

    if(deep[x]<deep[y])swap(x,y);

    int t=deep[x]-deep[y];

    for(int i=0;i<=15;i++)

        if(t&bin[i])x=fa[x][i];

    for(int i=15;i>=0;i--)

        if(fa[x][i]^fa[y][i])

            x=fa[x][i],y=fa[y][i];

    if(!(x^y))return y;

    return fa[x][0];

}

void Init()

{

    memset(vis,false,sizeof(vis));

    memset(nxt,0,sizeof(nxt));

    memset(first,0,sizeof(first));

    memset(fa,0,sizeof(fa));

}

int dis(int x,int y)

{

    int t=lca(x,y);

    return deep[x]+deep[y]-2*deep[t];

}

int solve(int a,int b,int c)

{

    int p1=lca(a,b),p2=lca(a,c),p3=lca(b,c),t;

    if(!(p1^p2))t=p3;

    else if(!(p2^p3))t=p1;

    else t=p2;

    int ans=dis(a,t)+dis(b,t)+dis(c,t);

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

}

int main()

{

    make_bin();

    Init();

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

    for(int i=1;i<=n-1;i++){

        scanf("%d%d",&u[i],&v[i]);

        nxt[i]=first[u[i]];

        first[u[i]]=i;

        u[i+n-1]=v[i],v[i+n-1]=u[i];

        nxt[i+n-1]=first[v[i]];

        first[v[i]]=i+n-1;

    }

    bfs();

    for(int a,b,c;m;m--){

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

        solve(a,b,c);

    }

    return 0;

}