最近公共祖先(LCA)
目录
最近公共祖先(LCA)
定义
求法
方法一：树上倍增
朴素算法
复杂度分析
方法二：dfs序与ST表
初始化与查询
复杂度分析
方法三：树链剖分
DFS序
性质
重链
重边
重子结点
剖分方法
剖分作用
复杂度分析
树链剖分拓展
最近公共祖先是树上的概念，不了解树的出门左转百度：树（数据结构名词）_百度百科
定义
假设我们需要求 x 和 y 的最近公共祖先，这里有多种等价的定义
路径x到y上深度最小的点
x和y公共祖先中深度最大的点
x和y在这棵树上距离最近的公共祖先结点
如果
x就是y的祖先，则x本身就是两者的最近公共祖先
求法
通常来说有四种
树上倍增
dfs序与ST表
树链剖分
Tarjan (离线算法)
这里我们只讨论前三种在线算法
方法一：树上倍增
倍增的思想可以看一下这篇文章：算法学习笔记(3): 倍增与ST算法
这是基于朴素方法的优化，所以在讲树上倍增之前我们还需要讲一下朴素的方法
朴素算法
选择x和y中深度较大的点，向上跳直到两者深度相同，然后两者同时向上跳直到两者第一次相遇，此时两者所在即是最近公共祖先
显然，我们每次只跳一个显然不优，所以借鉴倍增与二进制拆分的思想
令fa[x][k]指从x开始，向上跳2^k次所能达到的祖先，特别的，如果深度不够，则fa[x][k] = 0
那么，基于朴素算法的流程：我们只需要跳的时候利用倍增的思想就行了
这里给出一种参考代码：
notice: 这其实不是一种特别好的写法
int lca(int x, int y) {
int p;
// 这里保证了x是深度相对较大那一个
if (dep[x] < dep[y]) p = x, x = y, y = p;
// 将x跳到与y深度相同的位置
p = 0;
while (p >= 0) {
if (dep[fa[x][p]] >= dep[y]) x = fa[x][p], ++p;
else --p;
}
// 达到同样深度就已经相遇（y是x的祖先）
if (x == y) return x;
// 两者同时向上跳直到相遇
p = 0;
while (p >= 0) {
if (fa[x][p] != fa[y][p]) x = fa[x][p], y = fa[y][p], ++p;
else --p;
}
// 最后还要向上跳一个才是公共祖先
// 通过这种倍增写法得出的位置是最后一个满足if条件的位置！！！
return fa[x][0];
}
那么问题来了，如何初始化？
显而易见，跳2^k步相当于跳2次2^(k-1)步，所以有了
fa[x][i] = fa[fa[x][i - 1]][i - 1];
复杂度分析
在初始化的时候每一个点都需要O(logN)，那么总初始化需要O(NlogN)
在询问时，令k为x, y到最近公共祖先的最大距离，根据倍增算法，则复杂度为O(logk)，当树退化成一条链时，k最大取到n，那么最终复杂度应该为O(logN)
综上，初始化需要O(NlogN)，单次询问需要O(logN)
方法二：dfs序与ST表
这种方法相对难以理解，所以读者可以在掌握了一般的Tarjan缩点算法后再理解（这两个算法几乎没有关系，但是一些思想在Tarjan中有所体现)
下文中不是特别明白名词在后文中有所提及，或者可以参考讲解Tarjan算法的文章
先求出树每一个结点的dfn，不妨令x比y更先遍历到（dfn[x] < dfn[y]）
若x不是y的祖先
在
dfs序列中，区间[dfn[x], dfn[y]]内一定包含了LCA子树的部分，但不包含LCA及其祖先，并且该区间一定包含了LCA到y路径上的第一个儿子，而且它的深度是最小的
所以，我们只需要找到区间[dfn[x], dfn[y]]中深度最小的点，它的父结点就是LCA
若x是y的祖先，则x就是LCA，且x是区间[dfn[x], dfn[y]]中深度最小的点，与上述情况不太一样，那么考虑我们将x排除在区间外，则在区间[dfn[x] + 1, dfn[y]]中深度最小的点的父亲结点就是x。返回考虑第一种情况，由于第一种情况x一定不是LCA，那么将区间替换为[dfn[x] + 1, dfn[y]]不影响答案。
综上，我们只需要求区间[dfn[x] + 1, dfn[y]] 中深度最小的点的父结点即可。
初始化与查询
定义rdfn满足x == rdfn[dfn[x]]，ST表初始化时f[i][0] = rdfn[i]。
其实可以只需要
dfn就ok，f[dfn[i]][0] = i
定义区间操作
int Min(int x, int y) {
return depth[x] < depth[y] ? x : y;
}
定义查询操作
int query(int x, int y) {
if (x == y) return x; // 同一个结点啊
// 确保x是先遍历到的那一个结点
if (dfn[x] > dfn[y]) std::swap(x, y);
int k = log(dfn[y] - dfn[x]);
return Min(f[dfn[x] + 1][k], f[dfn[y] - (1<<k) + 1][k]);
}
其余的就套模板就行了
复杂度分析
初始化其实主要是ST表的初始化，所以初始化的复杂度为O(NlogN)（实际上应该是O(N + NlogN）
查询也是ST表的区间查询，复杂度为O(1)
方法三：树链剖分
好高级的名字……
树链剖分指将一棵树分割为若干条链，以维护树上信息。它包含重链剖分、长链剖分、实链剖分，在没有特殊说明的情况下，树链剖分一般指代重链剖分。这里也着重描述重链剖分。
这里先给出一些
DFS序
dfs序指dfs的顺序。具体方法是用一个计数变量cnt，遍历到结点x时，时间戳
dfn[x] = ++cnt，对应dfs序列中第cnt个就是x而上文定义中的
rdfn则可以在同时通过rdfn[cnt] = x记录下来
性质
结点的dfn大于其任意父结点
对于任意结点（包含本身）的子树中，存在一个dfn是连续的一条链
如果子树在dfs序列中是连续的一段，在维护子树（子树求和之类的子树操作）时，直接把它看做一个序列，那么就和在线段树上操作没有区别了
重链
相邻重边链接形成的链
重边
重子结点（如果有）与其父结点相连的边
重子结点
一个结点的子结点中度最大的结点（孩子个数最多的点）
剖分方法
重链剖分就是将每一条重链单独划分出来，从而通过dfn来维护链上信息
至于如何剖分，需要进行两次遍历
第一次遍历，获得所有节点的siz, dep, fa, son
这里
siz指结点的度，三个字符统一一下，fa是个例外，dep指结点的深度，fa指结点的父结点，son指结点的重子结点
第二次遍历，获得所有点的dfn, top
这里
dfn无需解释，top指结点所在重链最顶部的结点
思路清晰，这里给出一种参考写法
注意前提，点编号从
1 ~ n，且这里用的是前向星存图（树）
int top[N], dfn[N], son[N], dep[N], siz[N], fa[N];
// work son, siz, dep and fa
void workSSDF(int x, int par) {
dep[x] = dep[par] + 1, fa[x] = par, siz[x] = 1;
for (int y, i = head[x]; i; i = edge[i].next) {
y = edge[i].to;
if (y == par) continue;
workSSDF(y, x);
siz[x] += siz[y];
if (siz[y] >= siz[son[x]]) son[x] = y;
}
}
// work dfn and top
int cdfn = 0;
void workDT(int x, int ptop) {
dfn[x] = ++cdfn, top[x] = ptop;
if (son[x]) workDT(son[x], top[x]);
for (int y, i = head[x]; i; i = edge[i].next) {
y = edge[i].to;
if (!dfn[y]) workDT(y, y);
}
}
剖分作用
这么麻烦的求这个树链剖分有啥用？
如果我们随便画一个图并模拟一下上述过程……
graph TD;
A[结点编号]
1---2;
1---3;
3---4;
3---5;
3---7;
4---8;
8---9;
5---6;
在两次遍历完之后：
graph LR;
A[结点上的是dfn序]
subgraph 重链1
1 === 2;
2 === 3;
3 === 4;
4 === 5;
end
subgraph 重链2
6 === 7;
end
subgraph 重链3
2 --- 8
end
subgraph 重链4
1 --- 9
end
2 --- 6
考虑用纯markdown画图是真的难受，但树的结构是一样的……T^T
我们很容易发现，在同一条重链上的结点的dfn序是连续的……（这我们稍后在论述）
回到求LCA的流程，由于我们把树分为了从上到下的一些链
注意每一条链中没有深度相同的结点
所以，我们只需要不断的把两个结点通过top向上跳直到在同一条链上（此时top[x] == top[y]）
至于为什么要跳top结点的深度较大的结点……还请读者自行讨论
有一个需要注意的地方，不能直接
x = top[x]，因为top[top[x]] == top[x]!!!所以还需要跳到
top[x]的父节点上
流程清晰，这里给出一种参考代码
int lca(int x, int y) {
while (top[x] != top[y]) {
if (dep[top[x]] >= dep[top[y]]) x = fa[top[x]];
else y = fa[top[y]];
}
if (dep[x] <= dep[y]) return x;
return y;
}
复杂度分析
太难写了 Q^Q
依据重链的定义，每一条重链至少占了重链顶端结点所在的子树结点的\(logN\)个结点（一条链就占满了）
所以，剖分之后差不多是有\(logN\)条重链，所以每次询问至多跳\(logN\)次，所以……
初始化复杂度为O(N)(两次dfs)，查询复杂度为O(logN)
树链剖分拓展
看我的另一篇文章吧，太难写了，四千多个字呜啊
