算法图论

LCA,树上倍增,树上差分

字数统计: 2.5k字   |   阅读时长: 11分
,

$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