【洛谷 3379】最近公共祖先

题目描述

如题，给定一棵有根多叉树，请求出指定两个点直接最近的公共祖先。

输入格式

第一行包含三个正整数

接下来

输出格式

输出包含

输入输出样例

输入 #1

输出 #1

说明/提示

对于 $30%30\%30% 的数据，N≤10Nleq 10N≤10，M≤10Mleq 10M≤10。$

对于 $70%70\%70% 的数据，N≤10000Nleq 10000N≤10000，M≤10000Mleq 10000M≤10000。$

对于 $100%100\%100% 的数据，N≤500000Nleq 500000N≤500000，M≤500000Mleq 500000M≤500000。$

样例说明：

该树结构如下：

第一次询问：

第二次询问：

第三次询问：

第四次询问：

第五次询问：

故输出依次为

#include<cstdio>
#include<iostream>
#include<cmath>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
const int N=500005;
int head[N],cnt,n,m,T,x,y;
int dp[N],fa[N][22],lg[N];
struct node{
    int to,next;
}e[N];
void add(int x,int y){
    e[++cnt].to=y;
    e[cnt].next=head[x];
    head[x]=cnt;
}
void dfs(int now,int dad){
    fa[now][0]=dad; 
    dp[now]=dp[dad]+1;
    for(int i=1;i<=lg[dp[now]];i++)
        fa[now][i]=fa[fa[now][i-1]][i-1];
    for(int i=head[now];i;i=e[i].next)
        if(e[i].to!=dad) dfs(e[i].to,now);
}

int lca(int x,int y){
    if(dp[x]<dp[y]) swap(x,y);
    while(dp[x]>dp[y])
        x=fa[x][lg[dp[x]-dp[y]]-1];
    if(x==y) return x;
    for(int k=lg[dp[x]-1];k>=0;k--)
        if(fa[x][k]!=fa[y][k]) { x=fa[x][k]; y=fa[y][k]; }
    return fa[x][0];
}
int main(){
    freopen("3379.in","r",stdin);
    freopen("3379.out","w",stdout);
    scanf("%d %d %d",&n,&m,&T);
    for(int i=1;i<n;i++){
        scanf("%d %d",&x,&y);
        add(x,y); add(y,x);
    }
    for(int i=1;i<=n;i++)
        lg[i]=lg[i-1]+(1<<lg[i-1]==i);
    dfs(T,0);
    while(m--){
        scanf("%d %d",&x,&y);
        printf("%d
",lca(x,y));
    }
    return 0;
}