LCA【模板】

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 int tot,n,m,s,ver[2*5000010],head[2*500010],nxt[2*500010],f[500010][30],d[500010];
 4 void add(int x,int y){
 5     ver[++tot]=y;
 6     nxt[tot]=head[x];
 7     head[x]=tot;
 8 }
 9 void dfs(int u,int fa){
10     d[u]=d[fa]+1;
11     for(int i=1;(1<<i)<=d[u];i++)
12         f[u][i]=f[f[u][i-1]][i-1];
13     for(int i=head[u];i;i=nxt[i]){
14         int v=ver[i];
15         if(v==fa) continue;
16         f[v][0]=u;
17         dfs(v,u);
18     }
19 }
20 int LCA(int a,int b){
21     if(d[a]<d[b]) swap(a,b);
22     for(int i=20;i>=0;i--){
23         if(d[f[a][i]]>=d[b]) a=f[a][i];
24         if(a==b) return a;
25     }
26     for(int i=20;i>=0;i--)
27         if(f[a][i]!=f[b][i])
28             a=f[a][i],b=f[b][i];
29     return f[a][0];
30 }
31 int main(){
32     cin>>n>>m>>s;
33     for(int i=1;i<n;i++){
34         int x,y;
35         cin>>x>>y;
36         add(x,y);
37         add(y,x);
38     }
39     dfs(s,0);
40     while(m--){
41         int a,b;
42         cin>>a>>b;
43         cout<<LCA(a, b)<<endl;
44     }
45     return 0;
46 }