JZOJ 5257. 小X的佛光 (Standard IO)

5257. 小X的佛光 (Standard IO)

Time Limits: 2000 ms Memory Limits: 524288 KB

Description

Input

Output

Sample Input

3 3 1

1 2

2 3

1 2 3

1 1 3

3 1 3

Sample Output

1

1

3

Data Constraint

Hint

样例2、3、4见所附文件

题解

n个城市n−1条边，很明显是一颗树

画多几个图，就会发现可以用lca分类讨论

对于三个点x,z,y，要求的是x−>z和y−>z重合部分的长度，即点的个数

有三种情况

设三点lca分别是fxy，fyz，fxz

第一种是fxz=fyz，这样就是z的深度+/−fxz的深度+1

第二种是fxy=fyz，这样就是z的深度−fxz的深度+1

第三种是fxz=fxy，这样就是z的深度−fyz的深度+1

求lca用tarjan会爆栈，虽然我之前写过手打栈版，但是由于太麻烦了，就用了倍增

代码

#include<cstdio>

#include<cmath>

#include<algorithm>

#include<vector>

#include<queue>

#define N 200010

using namespace std;

vector<long>map[N];

queue<long>que;

bool b[N];

long dep[N],fa[N][20];

void build(long x)

{   long now,to,i;

    que.push(x);

    while(!que.empty()){

        now=que.front();

        que.pop();

        b[now]=true;

        for(i=0;i<map[now].size();i++){

            to=map[now][i];

            if(!b[to]){

                fa[to][0]=now;

                dep[to]=dep[now]+1;

                que.push(to);

            }

        }

    }

}

long n;

void init()

{   long i,j;

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

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

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

}

long lca(long x,long y)

{   long up;

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

        swap(x,y);

    up=19;

    while(dep[y]>dep[x]){

        while(dep[y]-(1<<up)<dep[x]&&up>=0)

            up--;

        if(up<0)break;

        y=fa[y][up--];

    }

    up=19;

    while(x!=y){

        while(fa[x][up]==fa[y][up]&&up>=0)

            up--;

        if(up<0)break;

        x=fa[x][up];

        y=fa[y][up];

        up--;

    }

    if(x==y)

        return x;

    else

        return fa[x][0];

}

int main()

{   long m,q,x,y,z,fxy,fxz,fyz,i,ans;

    scanf("%ld%ld%ld",&n,&m,&q);

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

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

        map[x].push_back(y);

        map[y].push_back(x);

    }

    build(1);

    init();

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

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

        fxy=lca(x,y);

        fxz=lca(x,z);

        fyz=lca(y,z);

        if(fxz==fyz&&fxz!=fxy)

            if(fxz==z)

                ans=dep[fxy]-dep[z]+1;

            else

                ans=dep[fxy]+dep[z]-dep[fxz]*2+1;

        else if(fxy==fyz&&fxz!=fxy)

            ans=dep[z]-dep[fxz]+1;

        else

            ans=dep[z]-dep[fyz]+1;

        printf("%ld\n",ans);

    }

    return 0;

}