LCA,树上倍增,树上差分

  |  

$1 LCA问题

lca

给定一棵有根树,若 z 既是 x 的祖先,又是 y 的祖先,则称 z 是 x,y 的最近公共祖先,记为 z = lca(x, y)

lca(x, y) 的两条重要性质:

  • lca(x, y) 是 x 到根的路径和 y 到根的路径的交点
  • lca(x, y) 是 x 到 y 的路径中顺度最小的节点

(1) 向上标记法

  • 从 x 向上走到根节点,记录所有经过的节点
  • 从 y 向上走,当走到标记过的节点时,即找到 lca(x, y)

每个查询均为 $O(N)$,如果是一次查询的话,就是这个算法,具体实现有很多方式。

模板问题:236. 二叉树的最近公共祖先 / 面试题 04.08. 首个共同祖先

两次搜索

第一次:从根节点开始,前序遍历找 p,记录过程中经过的节点

第二次:从 p 到根枚举记录的节点,问这个节点的子树上有没有 q,若有,则找到

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
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
class Solution {
public:
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
// 调用方保证树至少有两个点,且p,q有效
stack<TreeNode*> st;
_preOrder(root, st, p, q);

TreeNode *target;
if(st.top() == p)
target = q;
else
target = p;

TreeNode *cur = st.top();
st.pop();
if(cur -> left && dfs(cur -> left, target))
return cur;
if(cur -> right && dfs(cur -> right, target))
return cur;
TreeNode *prev = cur;
while(!st.empty())
{
cur = st.top();
st.pop();
if(cur -> left == prev && cur -> right && dfs(cur -> right, target))
return cur;
if(cur -> right == prev && cur -> left && dfs(cur -> left, target))
return cur;
prev = cur;
}
return nullptr;
}

private:
bool _preOrder(TreeNode* root, stack<TreeNode*>& st, TreeNode* p, TreeNode* q)
{
// 调用方保证 root 合法
st.push(root);

if(root == p || root == q)
return true;

if(root -> left && _preOrder(root -> left, st, p, q))
return true;
if(root -> right && _preOrder(root -> right, st, p, q))
return true;

st.pop();
return false;
}

bool dfs(TreeNode* root, TreeNode* target)
{
// 调用方保证 root 合法
if(root == target)
return true;

bool result = false;
if(root -> left)
result = result || dfs(root -> left, target);
if(result) return true;
if(root -> right)
result = result || dfs(root -> right, target);
return result;
}
};

递归

1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
if(!root || root == p || root == q) return root;
TreeNode *left = lowestCommonAncestor(root -> left, p, q);
TreeNode *right = lowestCommonAncestor(root -> right, p, q);
if(!left) return right;
if(!right) return left;
return root;
}
};

后序遍历

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
class Solution {
public:
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
if(!root) return nullptr;
TreeNode *lca = nullptr;
_postOrder(root, p, q, lca);
return lca;
}

private:
using PBB = pair<bool, bool>;
PBB _postOrder(TreeNode* node, const TreeNode* p, const TreeNode* q, TreeNode*& lca)
{
PBB result(false, false);
PBB left(false, false);
PBB right(false, false);
if(node -> left)
{
left = _postOrder(node -> left, p, q, lca);
if(lca) return left;
}
if(node -> right)
{
right = _postOrder(node -> right, p, q, lca);
if(lca) return right;
}
result.first = left.first || right.first;
result.second = left.second || right.second;
if(node == p)
result.first = true;
if(node == q)
result.second = true;
if(!lca && result.first && result.second)
lca = node;
return result;
}
};

(2) 树上倍增法

预处理 fa[x][k]

1
2
3
4
fa[x][k] := x 的第 (2 ^ k) 个祖先,即从 x 向上走 (2 ^ k) 步到达的节点。
若该节点不存在 fa[x][k] = 0
x 的父节点:fa[x][0]
fa[x][k] = fa[fa[x][k - 1]][k - 1]

查询 lca(x, y)

1
2
3
4
5
6
7
8
9
step1: d[x] := x 的深度, 不妨设 d[x] >= d[y]
step2: 按二进制划分的方式,把 x 向上调整到根 y 同一个深度
尝试从 x 向上走 k = 2^log(n), ..., 2^1, 1 步,若到达的节点深度比 d[y] 深,则 x = fa[x][k]
step3:
(1)此时若 x == y,则找到 lca,y 就是
(2)此时若 x != y,把 x, y 同时向上调整,保持深度一致
尝试从 x,y 同时向上走 k = 2^log(n), ..., 2^1, 1 步,若到达的节点 fa[x][k] != fa[y][k](仍未相交),则 x = fa[x][k], y = fa[y][k]
step4:
此时 x, y 必然只差一步相交,其父节点 fa[x][0] 即为 lca

预处理 $O(N\log N)$,一次查询 $O(\log N)$

代码实现

const vector<int>& d 为节点深度, const vector<vector<int>>& f 为倍增法预处理的祖先链

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
49
50
int lowbit(int n)
{
return n & (-n);
}

int highbit(int n)
{
int p = lowbit(n);
while(p != n)
{
n -= p;
p = lowbit(n);
}
return p;
}

int lca(int x, int y, const vector<int>& d, const vector<vector<int>>& f)
{
// d[x] >= d[y]
if(d[x] < d[y])
return lca(y, x, d, f);
// 将 y 向上调整直到和 x 一个深度
int delta = d[x] - d[y];
while(delta > 0)
{
x = f[x][log2(highbit(delta))];
delta -= highbit(delta);
}
if(x == y)
return x;
int n = d.size();
int m = log2(n);
while(true)
{
if(f[x][0] == f[y][0])
break;
int k = 1;
while(k <= m)
{
if(f[x][k] == -1 || f[y][k] == -1)
break;
if(f[x][k] == f[y][k])
break;
++k;
}
x = f[x][k - 1];
y = f[y][k - 1];
}
return f[x][0];
}

模板问题: 1483. 树节点的第 K 个祖先

本题为树上倍增法 LCA 的预处理 fa[x][k] 这一步

  • 倍增法
  • DFN序

力扣1483-树节点的第K个祖先

(3) tarjan 算法

最近公共祖先的 tarjan 算法本质是用并查集对向上标记法的优化。

它是离线算法,需要将 Q 个查询一次性读入,统一计算,统一输出,时间复杂度 $O(N + Q)$

DFS 过程中,维护所有节点的颜色

  • visited[i] = 0 : 节点 i 尚未访问到
  • visited[i] = 1 : 节点 i 已经访问到,但是尚未回溯
  • visited[i] = 2 : 节点 i 已经回溯

visited[i] == 1 的这些节点就是当前正在访问的节点及其祖先

当前节点为 x: x 到根的路径在 visited 中都标记为 1

若 y 是已经访问完毕并且回溯的节点,则 lca(x, y) 就是从 y 向上走到根,第一个遇到的标记为 1 的节点

利用并查集优化

当一个节点 x 被标记 2 时,把它所在的集合合并到它的父节点所在的集合中。此时 x 的父节点一定是标记为 1 的。此时查询 y 所在集合的代表元,就相当于从 y 向上走一直到一个开始递归但尚未回溯的节点,标记为 1,即 lca(x, y)

在 x 即将回溯前,x 与其父节点合并后,紧接着扫描与 x 相关的所有查询,若查询的另一节点 y 被标记为了 2,则 lca(x, y) = y 的代表元

$2 LCA 其它相关题目

1257. 最小公共区域

可以建出邻接表,但是不知道根,因此直接向上标记法不好用。

可以加一个超级源,把超级源与所有入度为 0 的点连边,然后将超级源视为根。

实现时用反图,将上述分析的超级源改为超级汇,入度改为出度,逻辑不变。

向上标记法求 lca 的代码如下(建图部分代码省略):

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
vector<vector<int>> g; // 反图
int root; // 超级汇

int lca(int x, int y)
{
unordered_set<int> path;
dfs1(x, root, path);
int lca = dfs2(y, path);
return lca;
}

bool dfs1(int u, const int t, unordered_set<int>& path)
{
path.insert(u);
if(u == t)
return true;
for(int v: g[u])
{
if(dfs1(v, t, path))
return true;
}
path.erase(u);
return false;
}

int dfs2(int u, const unordered_set<int>& path)
{
if(path.count(u) > 0)
return u;
for(int v: g[u])
{
int res = dfs2(v, path);
if(res != -1)
return res;
}
return -1;
}

235. 二叉搜索树的最近公共祖先

从根节点往下找,利用 BST 的性质

1123. 最深叶节点的最近公共祖先

后序遍历,找到所有最深的节点,在回溯阶段判断当前节点是不是答案。

$3 LCA 的应用

树上差分

区间操作: 区间加1 -> 端点操作: 左端点加1,右端点减1
差分序列的前缀和是原序列

将这个原理对应到树上,区间操作对应路径操作,前缀和对应子树和

次小生成树

先求出一颗最小生成树 mst,权和为 sum,将 mst 上的边标记为树边,其它的边标记为非树边

把非树边加入 mst 中,形成一个环,记加入的非树边为 (x, y, w),mst 上 x, y 之间的路径上的最大边权为 val1, 严格次大边权为 val2(val2 < val1)

  • w > val1 : 把 val1 对应的边替换为 (x, y, w) 这条边,得到一个候选答案,权和为 sum - val1 + w
  • w == val1 : 把 val2 对应的边替换为 (x, y, w) 这条边,得到一个候选答案,权和为 sum - val2 + w

枚举每条非树边,计算上述候选答案,更新全局答案

问题:如果和高效求出一条路径上的最大边权和严格次大边权 -> 用树上倍增进行预处理

1
2
3
fa[x][k] := x 的第 (2^k) 个祖先
dp[x][k][0] := x 到 fa[x][k] 的最大边权
dp[x][k][1] := x 到 fa[x][k] 的严格次大边权
1
2
3
4
5
6
7
8
9
fa[x][k] = fa[fa[x][k - 1]][k - 1]
dp[x][k][0] = max(dp[x][k - 1][0], dp[fa[x][k - 1]][k - 1][0])
dp[x][k][1] = max(dp[x][k - 1][1], dp[fa[x][k - 1]][k - 1][1]) dp[x][k - 1][0] = dp[fa[x][k - 1][k - 1][0]]
max(dp[x][k - 1][0], dp[fa[x][k - 1]][k - 1][1]) dp[x][k - 1][0] < dp[fa[x][k - 1][k - 1][0]]
max(dp[x][k - 1][1], dp[fa[x][k - 1]][k - 1][0]) dp[x][k - 1][0] > dp[fa[x][k - 1][k - 1][0]]
初始化
fa[x][0] = father(x)
da[x][0][0] = edge(x, father(x))
dp[x][0][1] = -INF

支配树

支配树


Share