树剖版lca

树剖版lca

树剖自带lca

#include<bits/stdc++.h>
using namespace std;
template<class T>inline bool read(T &x){
    x=0;register char c=getchar();
    while(!isdigit(c)){if(c==EOF)return false;c=getchar();}
    while(isdigit(c))x=(x<<3)+(x<<1)+(c^48),c=getchar();
    return true;
}
template<class T>inline void print(T x){
    if(x>9)print(x/10);
    putchar('0'+x%10);
}
const int MAXN=5e5+8;
int cnt,head[MAXN];
bool vis[MAXN];
struct Edge{int y,next;}mp[MAXN<<1];
void add(int u,int v){
    mp[++cnt].y=v;
    mp[cnt].next=head[u];
    head[u]=cnt;
}
int N,M,S;
int deep[MAXN],tot[MAXN],fa[MAXN],son[MAXN],top[MAXN];
int dfs1(int now,int pre,int dep){
    deep[now]=dep;
    tot[now]=1;
    fa[now]=pre;
    int max_son=-1;
    for(int i=head[now];i;i=mp[i].next){
        int to=mp[i].y;
        if(to==pre)continue;
        tot[now]+=dfs1(to,now,dep+1);
        if(tot[to]>max_son){
            max_son=tot[to];
            son[now]=to;
        }
    }
    return tot[now];
}
void dfs2(int now,int topfa){
    top[now]=topfa;
    if(!son[now])return;
    dfs2(son[now],topfa);
    for(int i=head[now];i;i=mp[i].next){
        int to=mp[i].y;
        if(!top[to])dfs2(to,to);
    }
}
int lca(int x,int y){
    while(top[x]!=top[y]){
        if(deep[top[x]]<deep[top[y]])swap(x,y);
        x=fa[top[x]];
    }
    if(deep[x]>deep[y])return y;
    return x;
}
int main() {
    read(N);read(M);read(S);
    int x,y;
    for(int i=1; i<N; ++i) {
        read(x);read(y);
        add(x,y);
        add(y,x);
    }
    dfs1(S,0,1);
    dfs2(S,S);
    while(M--){
        read(x);read(y);
        print(lca(x,y));
        putchar('
');
    }
    return 0;
}