最近公共祖先(LCA)

本文介绍求最近公共祖先的四种方法 包括倍增 树链剖分 RMQ(欧拉序) Tarjan离线

---

一.LCA定义

给定一棵树 以及树上两个节点 u, v 求它们的最近公共祖先 即深度最大且同时为 u, v 祖先的节点
例题:洛谷P3379

---

二. 求LCA

2.1 倍增法

关于倍增思想 参见倍增 及ST表&RMQ
思想:
先预处理每个 u 向上跳 2^k 步到达的祖先 f[u][k]
LCA:

1. 将深度较深的节点(图中u)向上跳到与另一个节点同深度(黄色节点)
2. 若节点相同 证明浅节点是二人的LCA 直接返回该节点
3. 否则 枚举 k 若 f[u][k] != f[v][k] 则向上跳 2^k 步
4. 最终它们的父节点就是LCA

即 先统一深度 再同时倍增跳跃

void dfs(int u, int f) { // 预处理
    fa[u][0] = f; // 当前节点向上1步为父节点
    // 倍增
    for (int k = 1; k <= lg[n]; k++) {
        fa[u][k] = fa[fa[u][k-1]][k-1];
    }
    for (auto v:g[u]) {
        if (v == f) continue;
        dep[v] = dep[u]+1; // 深度为父深度+1
        dfs(v, u);
    }
}
// lca
int query(int x, int y) {
    if (dep[x] < dep[y]) swap(x, y);
    // x为深度深的
    int dis = dep[x]-dep[y]; //到达同深度所需距离
    for (int k = lg[n]; k >= 0; k--) {
        // 即 深度差能被拆成多少个2^k
        if (dis & (1<<k)) {
            x = fa[x][k];
        }
    }
    // 此时同深度
    if (x == y) return x; // 若节点相等 则找到了
    // 一起跳
    for (int k = lg[n]; k >= 0; k--) {
        if (fa[x][k] != fa[y][k]) {
            x = fa[x][k];
            y = fa[y][k];
        }
    }
    return fa[x][0];
}

时间复杂度:
预处理: n个节点 logn的循环 O(nlogn)
查询: O(logn)
关于lg[n] (即log数组): 可参见倍增 及ST表&RMQ文末

---

2.2 树链剖分

思想:
将树划分为若干条重链 让节点一次跳一条链
几个概念:

• 重儿子: 一个节点的所有儿子中 子树大小最大的那个儿子
• 轻儿子: 除重儿子意外的其他儿子
• 重边: 父节点连向重儿子的边
• 轻边: 父节点连向轻儿子的边
• 重链: 由重边连接成的链 (每个节点最多属一条重链 轻儿子自身作为链头从而开始新的重链)
• 定义top[u]表示链头: u所在重链的顶端节点(深度最小的节点)

预处理:
两次dfs
第一次: 计算父亲 深度 重儿子 子树大小

void dfs1(int u, int f) {
    fa[u] = f; // 父
    dep[u] = dep[f] + 1; // 深度
    sz[u] = 1; // u为根子树大小
    son[u] = 0; // u的重儿子
    int maxsize = 0;
    for (int v:g[u]) {
        if (v == f) continue;
        dfs1(v, u);
        sz[u] += sz[v];
        if (sz[v] > maxsize) {
            maxsize = sz[v];
            son[u] = v;
        }
    }
}

第二次: 确定链头

void dfs2(int u, int tp) {
    top[u] = tp;
    if (son[u]) dfs2(son[u], tp); // 递归重儿子
    for (int v:g[u]) {
        if (v == fa[u]) continue;
        dfs2(v, v); // 轻儿子自己作为新链头
    }
}

LCA:
当两个节点不在同一条重链上 让链头深度大的节点跳到它链头的父亲(跨过一条轻边) 直到两节点在同一条重链上 此时深度小的节点就是LCA

int query(int x, int y) {
    while (top[x] != top[y]) {
        if (dep[top[x]] < dep[top[y]]) swap(x, y);
        // 此时x深度大
        x = fa[top[x]];// 跳到链头的父亲
    }
    // 返回深度小的
    return dep[x] < dep[y] ? x : y;
}

时间复杂度:
预处理n个节点 O(n)
单次查询 两点最差最近祖先为根节点 从任意节点到根节点最多跳logn条链 故为O(logn)

---

2.3 RMQ (欧拉序)

欧拉遍历: 对树进行dfs 每访问一个节点 (包括第一次进入和从子节点返回) 都记录一次该节点 得到一个序列 长度为 2(n-1)+1 (一共n-1条边 每条边贡献两次访问 进入递归还要记录一次根节点)
思想:
两节点的LCA是欧拉序列中两节点第一次出现位置之间的最小深度节点
因为从u到v的遍历过程 必定经过它们的LCA 欧拉序列中第一次出现 u 到第一次出现 v 的区间 包含了从 u 回溯到LCA再从LCA 到 v的完整路径 路径上只有深度最小节点为二者共同的祖先 明显 LCA就为这条路径的深度最小节点

那么 问题就被转化为给定区间内求深度最小的节点

然后,
ST表解决RMQ问题(上文给了链接)

定义几个数组:

• pos[u]: u第一次出现在欧拉序列中的下标
• euler[x] : 欧拉序列第t个节点
• dep[x]: 欧拉序列第t节点的深度

欧拉数组的长度是2n 所以开的时候开2*N

对于任意查询x,y

1. 设边界 l, r
2. 在深度数组对应区间找最小值下标idx
3. 答案为 euler[idx]

预处理:

void dfs(int u, int fa, int deep) {
    pos[u] = ++cnt; // 第一次出现位置
    euler[cnt] = u;
    dep[cnt] = deep;
    for (int v:g[u]) {
        if (v == fa) continue;
        dfs(v, u, deep+1);
        euler[++cnt] = u; // 回溯时再次记录 u
        dep[cnt] = deep;
    }
}
// 最终cnt = 2*n-1;

ST表:

int cmp(int a, int b) {
    return dep[a]<dep[b] ? a : b;
}
void build_st() {
    for (int i = 1; i <= cnt; i++) st[i][0] = i; // 初始区间为 i
    for (int j = 1; (1<<j) <= cnt; j++) {
        for (int i = 1; i+(1<<j)-1 <= cnt; i++) {
        	//st表找区间最小值
            st[i][j] = cmp(st[i][j-1], st[i+(1<<(j-1))][j-1]);
        }
    }
}

LCA:

int query(int x, int y) {
    int l = pos[x], r = pos[y];
    if (l > r) swap(l, r); //正确规定左右边界
    // 查询
    int k = lg[r-l+1];
    int idx=cmp(st[l][k], st[r-(1<<k)+1][k]);
    return euler[idx];
}

时间复杂度:
预处理ST表和dfs O(nlogn)
查询 O(1)

---

2.4 Tarjan离线

思想:
把查询数据离线储存 在一次dfs中同时处理所有查询 利用并查集维护当前已访问节点关系
对于每一次询问 记(u, v, id) id为询问的编号

步骤:

1. 对于节点 u 处理所有子节点v
2. 处理子节点之后 把v的并查集指向 u
3. 当 u 的所有子节点处理完毕 标记u为已访问
4. 遍历与 u 所有相关查询 (v, id)
   若 v 被访问过 那么find(v) 就为uv的LCA

解释:
当进行到第四步时 u的所有儿子处理完毕
此时看一个查询 (u, v) 若v被访问过 那么v只会在两个地方:

1. v在u 的某个子树中 此时find(v) = u LCA确实是u
2. 想象此时的 u 在某个根节点root的右子树 v可以在 root 的左子树里 由于我们刚刚从左子树过来 v的并查集老大就是 root 那么find(v) = root LCA确实是root
3. v在u的头上 此时在处理 u , v是u的祖先且并查集仍指向自己 find(v) = v 的确 是uv的LCA

关于算法名Tarjan: 跟强连通分量那个关系不大 这只是个人名 Tarjan这哥们很强发明了很多算法

void tarjan(int u, int fa) {
    for (int v:g[u]) {
        if (v == fa) continue;
        tarjan(v, u);
        merge(u, v);//并查集操作 子树 v 合并到 u
    }
    
    //step3:
    vis[u] = 1;
    for (auto [v, id]:query[u]) {
        if (vis[v]) {
            ans[id] = find(v); // 答案数组
        }
    }
}

!注意
查询数组双向存储 因为顺序不确定

时间复杂度
O(n+q)

---

2.5 一点小问题

我们四种求LCA的预处理或统计答案用的都是dfs 当树为一条链的时候极易爆栈
当 n>=1e5 时 就有可能爆了
这里给出一个倍增法bfs防爆栈写法 如果要用其他算法 那只能手写栈了

void bfs(int st) {
	queue<int> q;
	q.push(st);
	dep[st] = 1;
	fa[st][0] = 0;
	while (!q.empty()) {
		int u = q.front(); q.pop();
		for (auto v:g[u]) {
			if (v == fa[u][0]) continue;
			fa[v][0] = u; dep[v] = dep[u]+1;
			for (int k = 1; k <= lg[n]; k++) {
				fa[v][k] = fa[fa[v][k-1]][k-1];
			}
			q.push(v);
		}
	}
}

---

三. 总结

方法	预处理	查询	优点
倍增	O(nlogn)	O(logn)	通用 好理解
树链剖分	O(n)	O(logn)	常数小
RMQ	O(nlogn)	O(1)	查询O(1)
Tarjan	O(n+q)	离线	复杂度最优