1.定义
LCA（Least Common Ancestors），即最近公共祖先，指对于有根树 T 的两个结点 u 、v ，最近公共祖先 LCA(T, u, v) 表示一个结点 x, 满足 x 是 u、v 的祖先且 x 的深度尽可能大
$\space\space\space\space\space$ 例如下图所示
$$图中 LCA(2, 4) = 1, LCA(5, 6) = 2;$$
$\space\space\space\space\space$ 目前笔者所了解并掌握的有以下几种
- 向上标记法
- 用倍增求解 预处理时间复杂度 O(n log n) 每次查询的时间复杂度O(long n) 属于在线算法
- 采用tarjan算法 时间复杂度为O(n + m) 属于离线做法
后两者的区别在于
- 倍增的写法较为简单 是基于暴力的枚举优化 但时间上较tarja慢 是在线做法
- tarjan算法内容较多 不易书写 但速度较快 是离线做法
前置知识
1.能用dfs预处理出有根树中的父子关系和其到根节点的距离
void bfs(int root) // root 是根节点
{
memset(depth, 0x3f, sizeof depth);
depth[0] = 0, depth[root] = 1; //哨兵
int hh = 0, tt = 0; //模拟队列
q[0] = root;
while(hh <= tt)
{
int t = q[hh ++];
for(int i = h[t]; ~i; i = ne[i])
{
int j = e[i];
if(depth[j] > depth[t] + 1) //更新深度
{
depth[j] = depth[t] + 1;
q[++ tt] = j;
fa[j][0] = t; //倍增更新父子关系
for(int k = 1; k <= 15; k ++)
fa[j][k] = fa[fa[j][k - 1]][k - 1]; //递推 进入下一个状态
}
}
}
}
2.了解基础的倍增思想
倍增 从字面的上意思看就是成倍的增长 这是指我们在进行递推时 如果状态空间很大 通常的线性递推无法满足时间和空间复杂度的要求 那么我们就可以通过成倍的增长 只递推状态空间中在 2的整数次幂位置上的值作为代表 当需要其他位置上的值时2 我们只需要通过” 任意整数可以表示成若干个2的次幂项的和 ” 这一性质 例如 15 = $(1111)_2$ 即 15 = $2^0 + 2^1 + 2^2 + 2^3$ 然后使用之前预处理的值计算即可
我始终认为 这就是二进制枚举 二进制优化啊qaq
3.使用带路径压缩的并查集
int p[N];
for(int i = 1; i <= n; i ++) p[i] = i; //预处理
int find(int x)
{
if(p[x] != x) p[x] = find(p[x]);
return p[x];
}
4.熟悉链式前向星存图
int h[N], e[M], ne[M], idx;
memset(h, -1, sizeof h); //初始化
void add(int a, int b)
{
e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}
2.1向上标记法
思路
从x向上走到根节点 并标记所有经过的节点
从y向上走到根节点 当第一次遇到已标记的节点时 就找到了LCA(x, y)
对于每个询问 向上标记法的时间复杂度最坏为O(n)
分析
$\space\space\space\space\space$我们发现 在我们进行xy向上走的时候 一个一个的进行枚举标记在时间上太过于复杂 所以我们对枚举可以进行一种优化 一种二进制即倍增优化
2.2树上倍增法
2.2.1定义以及算法设计
$\space\space\space\space\space$最常用 也是最简单的算法 实质就是直接对暴力使用倍增优化将复杂度降低达到需求
$\space\space\space\space\space$树上倍增法是一个很重要的算法 除了求LCA之外 它在很多问题中都有广泛应用 我们假设F[x, y]表示x的$2_k$辈祖先 即从x向根节点走$2_k$步到达的节点 特别得 若该节点不存在 则另F[x, y] = 0， F[x, 0]就是x的父节点 除此之外 我们也可以找到递推方程 F[x, k] = F[F[x, k - 1], k - 1]
笔者认为 这个F函数最大的作用实际上就是记录路径
$\space\space\space\space\space$这类似于一个动态规划的过程 “阶段”就是节点的深度 因此 我们可以对树进行广度优先遍历 按照层次顺序 在节点入队之前 计算它在F数组中相应的值
$\space\space\space\space\space$以上部分是预处理 时间复杂度为O(n logn) 之后可以多次对不同的x y计算LCA 每次询问的时间复杂度为O(log n)
$\space\space\space\space\space$基于F数组计算LCA(x, y) 分为以下几步
$\space\space\space\space\space$1.设 depth[x] 为x的深度 不妨设 depth[x] $\geq$ depth[y] (否则交换xy)
$\space\space\space\space\space$2.用二进制插分思想 把x向上调整到与y同一深度
$\space\space\space\space\space$具体来说 就是依次尝试从x向上走k = $2^{log n} … 2 ^ 1, 2 ^ 0$步 检查到达的节点是否比y深 在每次检查中 若是 则另y = F[x, k]
$\space\space\space\space\space$3.若此时 x = y, 说明已经找到了LCA LCA = y
$\space\space\space\space\space$此种情况对应如下图
$\space\space\space\space\space$4.用二进制拆分思想 把x,y同时向上调整 并保持深度一致且二者不相会
$\space\space\space\space\space$具体来说 就是依次尝试把x,y同时向上走k = $2^{log n} … 2 ^ 1, 2 ^ 0$步 在每次尝试中 若F[x, k] $\neq$ Fy, k 则令 x = F[x, k], y = F[y, k]
$\space\space\space\space\space$5.当这些都完成后 此时 x，y必定只差一步就相会了 他们的父节点也即LCA就是F[x, 0]
2.2.2 算法模板
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];
}
2.2.3 算法疑问与分析
1. 为什么二进制拆分的时候 不直接在F[x, k] == F[y, k]结束 而反而是F[x, k] $\neq$ F[y,k]时候继续？
$\space\space\space\space\space$我们对如下图进行分析
$\space\space\space\space\space$本图就是一般形式上的fa[i][k]的一种表示 其中k 在本图中从0 -> 3(最大只有4个阶层 $2^3$ > 4)依次输出的祖先距离 可以知道 两个节点当F[x, k] == F[y, k]的时候 该点是x,y的祖宗节点 但不一定是最小 为什么这样说？ 我们对这个祖宗节点的路径进行抽象一下
$\space\space\space\space\space$我们可以惊奇的发现 在LCA上面所行走的路径 Fa[x, k] == Fa[y, k] 也即上图Fa表示中的最后相等的0的情况 所以 我们没办法通过Fa[x, k] == Fa[y, k]来进行判断 我们只能反向通过Fa[x, k] $\neq$ Fa[y, k]来进行改点的向上跳跃 知道最后不能再跳 则下一步就是LCA 即2.2.1-4的思路
2.对于倍增的用法
$\space\space\space\space\space$本题对于倍增的用法最大的作用是对于枚举的优化 使得从x -> y的枚举从O(n) -> O(logn) 同时 我们需要注意的是注意从高位开始枚举 而并非从低位 因为在枚举的时候 从低位开始 我们实际上不是向qmi那种转为2进制1中的情况确切的枚举 此处的枚举更像是一种拼凑 类比于找零的时候 先找最大的零钱 在找小的零钱 进而确保我们枚举拼凑的正确性
3.对于哨兵 depth[0] = 0 的作用
哨兵depth[0] = 0: 如果从i开始跳2^j步会跳过根节点
fa[fa[j][k-1]][k-1] = 0
那么fa[i][j] = 0 depth[fa[i][j]] = depth[0] = 0
如果我们不设置depth[0] = 0 那么在从i开始跳出根节点的时候 depth[fa[i][j]]] = 0x3f3f3f3f 即陷入一个诡异的界面
倍增源码
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 --) //a b向上跳跃
if(fa[a][k] != fa[b][k]) //只要父节点不相同就一直上跳
{
a = fa[a][k];
b = fa[b][k];
}
return fa[a][0];
}
例题一 祖孙询问
2.3 tanjan算法
2.3.1 定义
$\space\space\space\space\space$tanjan算法本质上是使用并查集对”向上标记法”的优化 它是一个离线算法 需要把m个询问一次性读入 统一计算 最后统一输出 时间复杂度为O(n + m)
在深度优先遍历的任意时刻 树中节点分为三类：
1.已经访问完毕并且回溯的节点 在这些节点上标记一个整数2
2.已经开始递归 但尚未回溯的节点 这些节点就是当前正在访问的节点x以及x的祖先 在这些节点上标记一个整数1
3.尚未访问的节点 这些节点没有标记
$\space\space\space\space\space$对于正在访问的节点x 它到根节点的路径已经标记为1 若y是已经访问完毕并且回溯的节点 则LCA(x, y)就是从y向上走到根 第一个遇到的标记为1的节点
$\space\space\space\space\space$可以利用并查集进行优化 当一个节点获得整数2的标记时 把它所在的集合合并到它的父节点所在的集合中(合并时它的父节点标记一定为1 且单独构成一个集合)
$\space\space\space\space\space$这相当于每个完成回溯的节点都有一个指针指向它的父节点 只需要查询y所在集合代表元素(并查集的get操作) 就等价于从y向上一直走到一个开始递归但尚未回溯的节点(具有标记1) 即LCA(x, y)
$\space\space\space\space\space$在x回溯之前 标记情况于合并情况如下图所示 黑色表示标记为1 灰色表示标记为2 白色表示没有标记 箭头表示执行了合并操作
$\space\space\space\space\space$此时扫描与x相关的所有查询 若询问当中的另一个点y的标记为2 就知道该询问的回答应该是y在并查集中的代表元素 (并查集中get(y)函数的结果)
2.3.2 算法
vector<PII> query[N]; // first 存查询的另外一个点 second 存查询编号
void tarjan(int u) //当前节点的编号为u
{
st[u] = 1;
for (int i = h[u]; ~i; i = ne[i])
{
int j = e[i];
if (!st[j])
{
tarjan(j);
p[j] = u; // 更新节点信息
}
}
for (auto item : query[u]) //遍历每个涉及节点U的情况
{
int y = item.first, id = item.second;
if (st[y] == 2) //如果y是已经标记并且回溯过 则直接输出
{
int anc = find(y);
// 存储相应的结果用来输出
}
}
st[u] = 2; //对 当前点进行标记
}
例题实例一 距离
总结
$\space\space\space\space\space$tarjan 时间复杂度为O(n+m)，也就是说在m很小的时候用倍增更优，在m较大的时候用Tarjan更优。
