LCA

自己打的

#include<bits/stdc++.h>
using namespace std;
struct edge{
int t,n;
edge(){
}
edge(int _t,int _n){
t=_t,n=_n;
}
};
edge e[500005<<1];
int head[500005],now=0;
int f[500005][20],mf;
int dipu[500005];
void addedge(int ff,int tt)
{
e[now]=edge(tt,head[ff]);
head[ff]=now++;
}
int ls1,ls2,ls3;
int n,m,s;
void dfs(int noden)
{
for(int i=head[noden];~i;i=e[i].n){
if(dipu[e[i].t])continue;
dipu[e[i].t]=dipu[noden]+1;
f[e[i].t][0]=noden;
for(int j=1;j<=mf;j++){
f[e[i].t][j]=f[f[e[i].t][j-1]][j-1];
}
dfs(e[i].t);
}
}
int lca(int aa,int bb)
{
if(dipu[aa]<dipu[bb])swap(aa,bb);
for(int i=mf;i>=0;i--)
if(dipu[f[aa][i]]>=dipu[bb])aa=f[aa][i];
if(aa==bb)return aa;
for(int i=mf;i>=0;i--){
if(f[aa][i]!=f[bb][i]){
aa=f[aa][i];
bb=f[bb][i];
}
}
return f[aa][0];

}
int main(){
memset(head,-1,sizeof(head));
memset(f,0,sizeof(f));
memset(dipu,0,sizeof(dipu));
scanf("%d%d%d",&n,&m,&s);
mf=(int)(log(n)/log(2))+1;
for(int i=1;i<n;i++){
scanf("%d%d",&ls1,&ls2);
addedge(ls1,ls2);
addedge(ls2,ls1);
}
dipu[s]=1;
dfs(s);
for(int i=1;i<=m;i++){
scanf("%d%d",&ls1,&ls2);
ls3=lca(ls1,ls2);
printf("%d ",ls3);
}


return 0;
}