LCA之树链剖分 zhn_666的lca 模板

#include <cstdio>
#include <algorithm>
#define N 500005
using namespace std;
int n,m,s,tot,dcnt;
inline int read(){
    int x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){
  if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int head[N*2],mp[N];
struct EDGE{
    int to,nex;
}ed[N*2];
struct tree{
    int son,fa,top,sz,s,e,dep;
}tr[N];
inline void add(int x,int y){
    ++tot;
    ed[tot].nex=head[x];
    head[x]=tot;
    ed[tot].to=y;
}
void dfs1(int u){
    tr[u].sz=1;
    for(int i=head[u];i;i=ed[i].nex){
        if(ed[i].to!=tr[u].fa){
            tr[ed[i].to].fa=u;
            tr[ed[i].to].dep=tr[u].dep+1;
            dfs1(ed[i].to);
            tr[u].sz+=tr[ed[i].to].sz;
            if(tr[ed[i].to].sz>tr[tr[u].son].sz)
              tr[u].son=ed[i].to;
        }
    }
}
void dfs2(int u,int top){
    tr[u].top=top;
    tr[u].s=++dcnt;
    mp[dcnt]=u;
    if(tr[u].son) {
        dfs2(tr[u].son,top);
        for(int i=head[u];i;i=ed[i].nex)
        if(ed[i].to!=tr[u].fa&&ed[i].to!=tr[u].son)
        dfs2(ed[i].to,ed[i].to);
    }
    tr[u].e=dcnt;
}
int find(int x,int y){
    int f1=tr[x].top;
    int f2=tr[y].top;
    while(f1!=f2){
        if(tr[f1].dep<tr[f2].dep){
            swap(f1,f2);
            swap(x,y);
        }
        x=tr[f1].fa;
        f1=tr[x].top;
    }
    if(tr[x].dep<tr[y].dep) return x;
    else return y;
}
int main(){
    n=read();m=read();
    s=read();
    for(int i=1;i<n;i++){
        int x,y;
        x=read();
        y=read();
        add(x,y);
        add(y,x);
    }
    tr[s].dep=0;
    dfs1(s);
    dfs2(s,s);
    for(int i=1;i<=m;i++){
        int x,y;
        x=read();
        y=read();
        printf("%lld\n",find(x,y));
    }
    return 0;
}

最稳的lca 写法哈哈哈