#include<bits/stdc++.h>
using namespace std;
const int N = (int)5e5+5; //
int fa[N][20];
vector<int> e[N];
int dep[N];
int n,m,s;
void add(int a,int b){
e[a].push_back(b);
e[b].push_back(a);
}
void dfs(int node,int father){
// 首先进行初始化
dep[node] = dep[father] + 1;
fa[node][0] = father;
for(int i=1;i<=19;i++){
fa[node][i] = fa[fa[node][i-1]][i-1];
}
// 开始对邻边进行操作
for(int u:e[node]){
if(u!=father) dfs(u,node);
}
}
int lca(int u,int v){
if(dep[u]<dep[v]) swap(u,v);
// 先跳到同一层
for(int i=19;i>=0;i--){
if(dep[fa[u][i]]>=dep[v]) u = fa[u][i];
}
if(u==v) return u; // 要特判一下
for(int i=19;i>=0;i--){
if(fa[u][i]!=fa[v][i]){
u = fa[u][i];
v = fa[v][i];
}
}
return fa[u][0];
}
int main(){
cin >> n >> m >> s;
int x,y;
for(int i=1;i<=n-1;i++){
cin >> x >> y;
add(x,y);
}
dfs(s,0);
for(int i=1;i<=m;i++){
cin >> x >> y;
cout << lca(x,y) << endl;
}
return 0;
}
我们再来看一个题目,也是关于公共祖先的,但是不是用到lca,反而有点像树形dp
#include<bits/stdc++.h>
using namespace std;
const int N = (int)1e4+5; //
int fa[N][12],dep[N];
vector<int> e[N];
int n,r,m;
int mp[N];
void add(int a,int b){
e[a].push_back(b);
e[b].push_back(a);
}
//void dfs(int u,int father){
// // 初始化
// fa[u][0] = father, dep[u] = dep[father]+1;
//
// for(int i=1;i<=11;i++) fa[u][i] = fa[fa[u][i-1]][i-1];
// for(int v:e[u]){
// if(v!=father){
// dfs(v,u);
// }
// }
//}
int dfs(int u,int father){
int ans = 0;// 节点数量
int cnt = 1;
for(int v:e[u]){
if(v!=father){
int s = dfs(v,u);
ans += cnt * s * 2;
cnt += s;
}
}
mp[u] = ans;
return cnt;
}
int lca(int u,int v){
if(dep[u]<dep[v]) swap(u,v);
for(int i=11;i>=0;i--){
if(dep[fa[u][i]]>=dep[v]) u = fa[u][i];
}
if(u==v) return u;
for(int i=11;i>=0;i--){
if(fa[u][i]!=fa[v][i]) u = fa[u][i], v = fa[v][i];
}
return fa[u][0];
}
int main(){
cin >> n >> r >> m;
int x,y;
for(int i=1;i<=n-1;i++){
cin >> x >> y;
add(x,y);
}
dfs(r,0);
for(int i=1;i<=n;i++){
for(int j=0;j<=11;j++){
mp[fa[i][j]] ++;
}
}
// for(int i=1;i<=n;i++){
// for(int j=i+1;j<=n;j++){
// mp[lca(i,j)] ++;
// }
// }
for(int i=1;i<=m;i++){
int x;
cin >> x;
cout << mp[x] +1 << endl;
}
return 0;
}