模板题
首先我们要要处理一个数组 fa 。
fa_{i,j} 表示第 i 个点向上 2^j 条边的节点。
再预处理一个深度。
这一个 dfs 即可解决
void dfs(int x,int father)
{
dep[x]=dep[father]+1;
fa[x][0]=father;
for(int i=1;i<=19;++i) fa[x][i]=fa[fa[x][i-1]][i-1];
for(auto i:v[x])
{
if(i==father) continue;
dfs(i,x);
}
}
解下来就是 lca 的核心了。
给出两个点求LCA。
我们先让深度大的点往上跳，一直跳到和另一个点深度相等
if(dep[x]<dep[y]) swap(x,y);//我们强制让x深度大
for(int i=19;i>=0;--i)
if(dep[fa[x][i]]>=dep[y]) x=fa[x][i];
这时我们特判 x=y 就直接返回 x
解下来我们两个点一起跳，只要父亲不同就跳，这个时候我们就会跳到答案的儿子，接下来做什么不用我多说。
for(int i=19;i>=0;--i)
if(fa[x][i]!=fa[y][i])
{
x=fa[x][i];
y=fa[y][i];
}
return fa[x][0];
点赞破5，讲两道例题。
