「Day-4 提高笔记-LCA最近公共祖先」

#include<iostream>
using namespace std;const int MAXN = 5 * 1e5 + 5;
struct node{int to,next;
}e[MAXN * 2];
int f[MAXN][20],dp[MAXN];//f[x][i] 表示 x 的第2^i个节点的编号 
int h[MAXN * 2],tot = 0;
int n,m,s;
void add(int x,int y){e[++ tot] = {y,h[x]};h[x] = tot;
}
void dfs(int x,int fa){dp[x] = dp[fa] + 1;f[x][0] = fa;//f[x][0] = x的第1(2^0)个父节点的节点编号 for(int i = 1;(1 << i) <= dp[x];i ++){f[x][i] = f[f[x][i - 1]][i - 1];}for(int i = h[x];i;i = e[i].next){int to = e[i].to;if(to != fa){dfs(to,x);}}return;
}
int u,v;
int LCA(int x,int y){if(dp[x] < dp[y]) swap(x,y);for(int i = 19;i >= 0;i --){if(dp[x] - (1 << i) >= dp[y]){x = f[x][i];}}if(x == y) return x;for(int i = 19;i >= 0;i --){if(f[x][i] != f[y][i]){x = f[x][i];y = f[y][i];}} return f[x][0];
}int main(){cin >> n >> m >> s;for(int i = 1;i <= n - 1;i ++){cin >> u >> v;add(u,v); add(v,u); }dfs(s,0);for(int i = 1;i <= m;i ++){cin >> u >> v;cout << LCA(u,v) << '\n';}return 0;
}