https://www.luogu.org/problemnew/show/P3379
1 #include<iostream> 2 #include<cstdio> 3 using namespace std; 4 int m, n, root; 5 struct qwq{ 6 int t, nex; 7 }edge[2*500001]; 8 int d[500001], f[500001][25], head[500001];//d数组记录深度 9 int cnt; 10 void add(int x, int y){//链式前向星存图 11 edge[++cnt].t=y; 12 edge[cnt].nex=head[x]; 13 head[x]=cnt; 14 } 15 void dfs(int a, int ft){//预处理 16 d[a]=d[ft]+1; 17 for(int i=0; i<=20; i++) 18 f[a][i+1]=f[f[a][i]][i]; 19 for(int i=head[a]; i; i=edge[i].nex){ 20 int v=edge[i].t; 21 if(v==ft) continue; 22 f[v][0]=a; 23 dfs(v, a); 24 } 25 } 26 int lca(int x,int y){ 27 if(d[x]<d[y]) swap(x,y);//默认把x往上跳 28 for(int i=21; i>=0; i--){ 29 if(d[f[x][i]]>=d[y]) x=f[x][i]; 30 if(x==y) return x; 31 } 32 for(int i=21; i>=0; i--) 33 if(f[x][i]!=f[y][i]) x=f[x][i], y=f[y][i]; 34 return f[x][0]; 35 } 36 int main(){ 37 scanf("%d%d%d",&n,&m,&root); 38 for(int i=1; i<n; i++){ 39 int x, y; 40 scanf("%d%d",&x,&y); 41 add(x, y); 42 add(y, x); 43 } 44 dfs(root, 0); 45 for(int i=1; i<=m; i++){ 46 int x, y; 47 scanf("%d%d",&x,&y); 48 printf("%d ",lca(x,y)); 49 } 50 return 0; 51 }