大家好，又见面了，我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

Jetbrains全系列IDE使用 1年只要46元 售后保障 童叟无欺

最近公共祖先

带查询的节点为x和y节点，书的深度为d

1. 暴力求解：设置访问数组vis[N],以此遍历x的父节点并做标记，然后再遍历y的父节点，第一个被做标记的就是公共祖先，时间复杂度为O(d)
2. 倍增法：f[i][j]代表当前节点向上走$2^j$所能走到的节点，其中$0\le j\le \lceil log(d)\rceil$，时间复杂度为O(logn)，另外还需要设置dist[N]代表节点i到根的距离+1，哨兵：如果从i开始跳$2^j$步会跳过根节点，那么f[i][j] = 0,dist[root]=0
3. Tarjan离线算法：将每一个搜索过的点归类到他的代表节点中去，代表节点就是搜索过的节点与当前节点的公共祖先。时间复杂度O(n)

倍增法

1. 先将两个点跳到同一层
2. 再让两个点往上跳，一直跳到他们的公共祖先的下一个几点。我们跳的时候是基于二进制拼凑的思想，从最高位到最低位判断。

预处理f[i][j]时间复杂度：nlog(n)
查询O(logn)

倍增法(bfs)代码

int fa[N][16],depth[N];
int q[N],hh = 0,tt = 0;
int head[N],cnt;
struct Edge{ 

int v,next;
}edge[M];
void add(int u,int v){ 

edge[cnt].v = v;
edge[cnt].next = head[u];
head[u] = cnt ++;
}
void bfs(int root){ 
     //预处理
memset(depth,INF,sizeof depth);
q[0] = root;
depth[0] = 0;
depth[root] = 1,fa[root][0] = 0;
while(hh <= tt){ 

int t = q[hh ++];
for(int i = head[t];~i;i = edge[i].next){ 

int ver = edge[i].v;
if(depth[ver] < depth[t] + 1)continue;
depth[ver] = depth[t] + 1;
q[++ tt] = ver;
fa[ver][0] = t;
for(int k = 1;k < 16;k ++){ 

fa[ver][k] = fa[fa[ver][k - 1]][k - 1];
}
}
}
}
int lca(int a,int b){ 

if(depth[a] < depth[b])swap(a,b);
for(int k = 15;k >= 0;k --)
if(depth[fa[a][k]] >= depth[b])
a = fa[a][k];
if(a == b)return a;
for(int k = 15;k >= 0;k --)
if(fa[a][k] != fa[b][k]){ 

a = fa[a][k];
b = fa[b][k];
}
return fa[a][0];
}

Tarjan

struct Edge{ 

int v,next;
}edge[M];
void add(int u,int v){ 

edge[cnt].v = v;
edge[cnt].next = head[u];
head[u] = cnt ++;
}
void init(){ 

for(int i = 0;i < N;i ++)fa[i] = i;
}
int Find(int x){ 

return fa[x] = (fa[x] == x ? x : Find(fa[x]));
}
void Tarjan(int u,int f){ 

vis[u] = true;
for(auto &q : query[u]){ 

int y = q.x,id = q.y;
if(vis[y])res[id] = Find(y);    //如果之前遍历过另一个节点
}
for(int i = head[u];~i;i = edge[i].next){ 

int ver = edge[i].v;
if(ver == f)continue;
Tarjan(ver,u);
fa[ver] = u;
}
}