洛谷 P3379 lca 模板题
#include<iostream> #include<cstring> #include<algorithm> #include<cstdio> #include<vector> using namespace std; int n,m,r,a,b; int deep[500005],fa[500005],f[500005][35]; bool vis[500005]; vector< vector<int> > v(500005); void dfs(int u,int cnt){ deep[u] = cnt; vis[u] = true; for (int i=0;i<v[u].size();i++) if (!vis[v[u][i]]) dfs(v[u][i], cnt + 1); } void pre(){ for (int i=1;i<=n;i++){ if (i == r) continue; for (int j=0;j<v[i].size();j++){ if (deep[v[i][j]] + 1 == deep[i]) { fa[i] = v[i][j]; break; } } } for(int i=0;i<=20;i++) f[r][i] = 0; for(int i=1;i<=n;i++) if (i != r) f[i][0] = fa[i]; for(int k=1;k<=20;k++) for(int i=1;i<=n;i++) f[i][k] = f[f[i][k-1]][k-1]; } int jump(int u,int step){ for (int k=0;k<=20;k++) if ((step & (1 << k))) u = f[u][k]; return u; } int qlca(int u,int v){ if (deep[u] < deep[v]) swap(u,v); u = jump(u, deep[u] - deep[v]); for (int k=20;k>=0;k--) if (f[u][k] != f[v][k]) u = f[u][k], v = f[v][k]; return u == v ? u : fa[u]; } int main(){ scanf("%d%d%d",&n,&m,&r); for (int i=0;i<n-1;i++){ scanf("%d%d",&a,&b); v[a].push_back(b); v[b].push_back(a); } dfs(r,0),pre(); for (int i=0;i<m;i++){ scanf("%d%d",&a,&b); printf("%d\n",qlca(a,b)); } return 0; }
