最近公共祖先
c++代码
#include<bits/stdc++.h>
using namespace std;
constexpr int N =5E5 + 10;
struct edge{
int to, next; //两个整型成员变量 to 和 next。这个结构体表示了图中的一条边,其中 to 表示边的终点,
//next 表示下一条以同一个起点为起始点的边的索引。
}edge[N << 1];
int head[N << 1], cnt;//head[]一直在更新(u,v)中在edge[]的下标位置,cnt表示第几条边
//注意由于是无向图所以(u,v)需要存储两条边
void addEdge(int u, int v){
edge[++cnt].to = v;
edge[cnt].next = head[u];
head[u] = cnt;
}
int deep[N], fa[N][20];//deep[x]表示x的深度,fa[x][],father是x的父节点
void dfs(int x, int father){
deep[x] = deep[father] + 1;//深度比父节点加一
fa[x][0] = father;//记录x的父节点
for(int i = 1; (1 << i) < deep[x] ; i++){//1向左移i就相当于1*2^i=2^i,就是在判断当前深度能不能跳2^i步
fa[x][i] = fa[fa[x][i-1]][i-1]; //记录父节点
}
for(int i = head[x]; i; i = edge[i].next){//遍历x的所有孩子节点
if(edge[i].to != father){
dfs(edge[i].to, x);
}
}
}
int LCA(int u, int v){
if(deep[u] < deep[v]){
swap(u, v);//让u是深度较大的点
}
//先让u跳到和v相同的高度,然后一起往上跳
for(int i = 19; i >= 0; --i){//2^19 > 5e5 +10
//一开始 2^i过于大不会进入if判断
if(deep[u] - deep[v] >= (1 << i)){//防止u跳过头换一个较小的i
u = fa[u][i]; //更新 u
}
}
if(u == v){ //v就是u的祖先
return u;
}
//u,v同时往上跳找到LCA
for(int i = 19; i >= 0; --i){
if(fa[u][i] != fa[v][i]){//找到共同祖先之后就不会进入if
u = fa[u][i];
v = fa[v][i];
}
}
return fa[u][0];
// 最后 x 位于 LCA 的下一层, 父节点 fa[x][0] 就是 LCA
}
int main(){
//N族谱人数,Q工作人员挑选对数
int n, q, s = 1;
cin >> n >> q;
for (int i = 1; i <= n - 1; i++) {
int x, y;
cin >> x >> y;
addEdge(x, y); addEdge(y, x);//无向图
}
dfs(s, 0);//从根节点开始搜
for (int i = 1; i <= q; i++) {
int x, y;
cin >> x >> y;
cout << LCA(x, y) << endl;
}
return 0;
}
输入:
3 1
1 2
1 3
2 3
输出:
1