树上倍增

  |  

摘要: 树上倍增算法及其在最近公共祖先问题上的应用

【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】
我的网站:潮汐朝夕的生活实验室
我的公众号:算法题刷刷
我的知乎:潮汐朝夕
我的github:FennelDumplings
我的leetcode:FennelDumplings


在文章 树的直径 中我们学习了树的直径的算法,这是树上的一个基础问题,很多问题都可以拆解成树的直径问题。

树上的另一个很常见的基础问题是最近公共祖先问题,同样有很多问题需要依赖最近公共祖先的解。最近公共祖先问题是这样说的,给定一棵树,然后给定树上的两个节点,要求返回这两个节点的最近公共祖先节点。给定一棵树如果只有一次查询,那么直接通过树的遍历解决即可,如果查询有很多次,就不能每次查询都遍历了,需要想出高效的办法,主流的有树上倍增和 Tarjan 两种。

本文我们首先学习一下树上倍增的算法思想,然后以力扣 1483 题(第 193 场周赛 D 题)为模板题,讲解树上倍增法及其代码模板,此外本题还有 DFN 序的解法,也很经典,相关的概念在上一篇文章 遍历序的概念与性质 中介绍过。在本题的基础上稍微再增加一些操作,就是最近公共祖先问题的树上倍增解法,最后会简要提一下。

树上倍增

树上倍增是一种树上的常见算法,主要解决从某个节点向上找第 k 辈祖先的问题,在此基础上可以进一步解决最近公共祖先问题。此外树上倍增还可以在很多问题中有所应用。

设 $dp[u][k]$ 为节点 $u$ 往上数 $2^k$ 个祖先,也就是从 $u$ 向根节点走 $2^{k}$ 到达的节点,若该点不存在则 $dp[u][k] = 0$。$dp[u][0]$ 为 $u$ 的父节点。此外对于 $\forall k \in [1, \log n]$,有以下关系:

这是一个动态规划的过程,阶段是节点 $u$ 的深度。因此可以对树进行 BFS,按照层序,在节点 $u$ 入队之前,计算 $dp[u][k]$ 的值。

以上是预处理过程,时间复杂度为 $O(N\log N)$,此后可以多次对不同的节点 $u$ 求它的第 $k$ 辈祖先,过程见后面的题解。

题目

给你一棵树,树上有 n 个节点,按从 0 到 n-1 编号。树以父节点数组的形式给出,其中 parent[i] 是节点 i 的父节点。树的根节点是编号为 0 的节点。

请你设计并实现 getKthAncestor(int node, int k) 函数,函数返回节点 node 的第 k 个祖先节点。如果不存在这样的祖先节点,返回 -1 。

树节点的第 k 个祖先节点是从该节点到根节点路径上的第 k 个节点。

1
2
3
4
5
1 <= k <= n <= 5*10^4
parent[0] == -1 表示编号为 0 的节点是根节点。
对于所有的 0 < i < n ,0 <= parent[i] < n 总成立
0 <= node < n
至多查询 5*10^4 次

示例:

输入:
[“TreeAncestor”,”getKthAncestor”,”getKthAncestor”,”getKthAncestor”]
[[7,[-1,0,0,1,1,2,2]],[3,1],[5,2],[6,3]]

输出:
[null,1,0,-1]

解释:
TreeAncestor treeAncestor = new TreeAncestor(7, [-1, 0, 0, 1, 1, 2, 2]);

treeAncestor.getKthAncestor(3, 1); // 返回 1 ,它是 3 的父节点
treeAncestor.getKthAncestor(5, 2); // 返回 0 ,它是 5 的祖父节点
treeAncestor.getKthAncestor(6, 3); // 返回 -1 因为不存在满足要求的祖先节点

题解

最近公共祖先(LCA)问题的在线询问常用倍增法做,此外还有一种基于 DFN 序的思路。

算法1:树上倍增

每个节点上保存一些信息:该节点的第 k 个祖先,当 $k = 0, 1, 2, 4, 8, \cdots$ 时的祖先 id 保存下来。

即 $2^{j}$ , $j = 0, 1, 2, 3, \cdots$ 数据范围有 $n <= 5e4$, j 最大取 16 就够用。

维护预处理信息 fa[i][j] := 第 i 节点向上走 $2^[j]$ 的祖先。

考虑 getKthAncestor(i, k) 从 i 点向上跳 k 步时,可以根据 k 的二进制分解来跳。

所有的中间点和终点都可以直接查询 fa 得到。

例如跳 k = 11 步,二进制为 1011,按以下顺序跳:

  • 第一位为 1 -> 先跳 1 步($2^{0}$),到达中间点 i1。
  • 第二位为 1 -> 再跳 2 步($2^{1}$),到达中间点 i2。
  • 第三位为 0 -> 当前这 4 步不跳,跳过($2^{2}$),到达中间点 i3。
  • 第四位为 1 -> 跳 8 步($2^{3}$),到终点 u。

fa 的计算: 求 f[i][j] 时,f[i][j - 1] 已经求完,可以将 j 拆成两个 j - 1 调用结果,但是要注意一个 j - 1 就可能走到 -1 了,需要判定一下。

1
2
3
4
5
fa[i][0] = parent[i]
fa[0][j] = -1

若 fa[i][j - 1] = -1,则 fa[i][j] = -1
若 fa[i][j - 1] != -1,则 fa[i][j] = fa[fa[i][j - 1]][j - 1]

代码 (C++,模板)

构造函数中,给定各个节点的父节点,也就是 parent 数组,预处理 fa 的代码模板。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
class TreeAncestor {
public:
TreeAncestor(int n, vector<int>& parent) {
// fa[i][j] := 从 i 爬 2 ^ j 步所到点的 id
// fa[i][0] := 从 i 爬 1 不所到点的 id
fa = vector<vector<int> >(n, vector<int>(M));
for(int i = 0; i < n; ++i)
fa[i][0] = parent[i];
for(int j = 1; j < M; ++j)
fa[0][j] = -1;
for(int j = 1; j < M; ++j)
for(int i = 0; i < n; ++i)
{
if(fa[i][j - 1] == -1)
fa[i][j] = -1;
else
fa[i][j] = fa[fa[i][j - 1]][j - 1];
}
}

int getKthAncestor(int node, int k) {
for(int i = M - 1; i >= 0; --i)
{
if(k & (1 << i))
node = fa[node][i];
if(node == -1)
break;
}
return node;
}

private:
const int M = 16;
vector<vector<int> > fa;
};

算法2:DFN序

对树遍历,每到一个点,按顺序给点编一个号,该编号称为 dfn 序。

DFN 序的好的性质:任取一个子树,根节点的号是最小的,并且同一棵子树中的 dfn 序连续。

对于 getKthAncestor(i, k): 某点 i,其 dfn 序为 a,level 为 d, 要往上跳 k,则目标点的 level 为 d - k。

根据 dfn 序的两条性质,对于同一 level 中的点,包含点 i 的子树根的 dfn 序肯定小于 a,同时也是所有小于 a 的 dfn 序中最大的。

例如图中例子:a = 7, d = 4, k = 2, $d^{‘} = d - k = 2$,第二层的 dfn 序为 2, 8,其中 2 是小于 7 中的最大的,因此答案为 dfn 序为 2 对应的节点。

代码(C++)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
class TreeAncestor {
public:
TreeAncestor(int n, vector<int>& parent) {
g = vector<vector<int> >(n);
for(int node = 1; node < n; ++node)
g[parent[node]].push_back(node);
id = vector<int>(n, -1);
nodeid = vector<int>(n, -1);
level_dfnids = vector<vector<int>>();
node_level = vector<int>(n, -1);
int dfnid = 0;
dfs(0, dfnid, 0);
}

int getKthAncestor(int node, int k) {
int level = node_level[node];
int ancestor_level = level - k;
if(ancestor_level < 0)
return -1;
int dfnid = id[node];
// 大于等于 dfnid 的最小 it
auto it = lower_bound(level_dfnids[ancestor_level].begin(), level_dfnids[ancestor_level].end(), dfnid);
int ancestor_dfnid = *(--it);
return nodeid[ancestor_dfnid];
}

private:
vector<int> id; // nodeid -> dfnid
vector<int> nodeid; // dfnid -> nodeid
vector<int> node_level; // nodeid -> level
vector<vector<int>> level_dfnids; // level -> dfnids
vector<vector<int>> g; // 邻接表

void dfs(int node, int& dfnid, int level)
{
id[node] = dfnid;
nodeid[dfnid] = node;
if((int)level_dfnids.size() <= level)
level_dfnids.push_back({});
level_dfnids[level].push_back(dfnid);
node_level[node] = level;
for(int son: g[node])
{
dfnid += 1;
dfs(son, dfnid, level + 1);
}
}
};

最近公共祖先 (LCA) 问题

LCA 问题是要求节点 A, B 的最近公共祖先,需要在上题第基础上继续做。

LCA 问题一般分为两步:

第一步是将比较深的点 B 跳到与 A 同一 level,这一步刚好就是本题做的某点的第 k 个祖先。

第二步是将 A, B,同时往上跳,每次跳 $2^[k]$ 步,分别到 u1 和 u2,这里从大到小枚举 k 判断跳 $2^{k}$ 是否使得 u1 != u2,取使得 u1 != u2 的最大的 k, 因为 u1 = u2 的话,就跳到 LCA 的上面了。

重复第二步直到 A, B 的父节点相同,该父节点就是最近公共祖先。


Share