算法图算法

最近公共祖先问题

字数统计: 5.1k字   |   阅读时长: 23分
, , ,

摘要: 最近公共祖先问题的三种解法，以及一些应用

【对数据分析、人工智能、金融科技、风控服务感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：潮汐朝夕
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

在文章 树上倍增 中，我们学习了树上倍增的思想。树上倍增主要解决从某个节点向上找第 k 辈祖先的问题，在此基础上可以进一步解决最近公共祖先等问题。

本文我们就来看一下最近公共祖先(LCA)问题的几种解法，然后解决力扣 1257。

LCA问题描述

lca

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

z = lca(x, y) 有两条重要性质：

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

最近公共祖先问题就是给定任意两个不同的节点 x, y，要求返回 x 和 y 的最近公共祖先节点 z。下面我们分别看 LCA 问题的三种解法：向上标记法、树上倍增法、Tarjan算法。

向上标记法

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

每个查询均为 $O(N)$，如果是一次查询的话，就是这个算法，具体实现有很多方式，比如两次搜索、递归、后序遍历。下面通过模板题来看。

模板题

给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。

提示：

1
2
3
4
5
树中节点数目在范围 [2, 1e5] 内。
-1e9 <= Node.val <= 1e9
所有 Node.val 互不相同 。
p != q
p 和 q 均存在于给定的二叉树中。

示例 1：
输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
输出：3
解释：节点 5 和节点 1 的最近公共祖先是节点 3 。
示例 2：
输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
输出：5
解释：节点 5 和节点 4 的最近公共祖先是节点 5 。因为根据定义最近公共祖先节点可以为节点本身。
示例 3：
输入：root = [1,2], p = 1, q = 2
输出：1

代码1：两次搜索

第一次：从根节点开始，前序遍历找 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;
    }
};

代码2：递归

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;
    }
};

代码3：后序遍历

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;
    }
};

树上倍增法

树上倍增法的算法原理可以参考文章 树上倍增，这里直接给出在树上倍增法基础上解决 LCA 问题的算法。

首先通过树上倍增法预处理 fa[x][k]，表示节点 x 的第 k 辈祖先的节点。预处理的过程是一个动态规划：

1
2
3
4
5
6
7
状态定义：
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]

其中 k 的范围为从 0 到 $\left\lceil\log{n}\right\rceil$。

预处理好 fa[x][k] 后，查询 z = lca(x, y) 的 $\left\lceil\frac{b}{a}\right\rceil$ 过程如下：

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>>& fa 为倍增法预处理的祖先链。

在 d 和 fa 已经预处理好之后，求 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
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>>& fa)
{
    // d[x] >= d[y]
    if(d[x] < d[y])
        return lca(y, x, d, fa);
    // 将 y 向上调整直到和 x 一个深度
    int delta = d[x] - d[y];
    while(delta > 0)
    {
        x = fa[x][log2(highbit(delta))];
        delta -= highbit(delta);
    }
    if(x == y)
        return x;
    int n = d.size();
    int m = log2(n);
    while(true)
    {
        if(fa[x][0] == fa[y][0])
            break;
        int k = 1;
        while(k <= m)
        {
            if(fa[x][k] == -1 || fa[y][k] == -1)
                break;
            if(fa[x][k] == fa[y][k])
                break;
            ++k;
        }
        x = fa[x][k - 1];
        y = fa[y][k - 1];
    }
    return fa[x][0];
}

模板题

给定一棵有根多叉树，请求出指定两个点直接最近的公共祖先。

1
2
3
4
5
6
7
8
9
输入格式
第一行包含三个正整数 N,M,S，分别表示树的结点个数、询问的个数和树根结点的序号。

接下来 N−1 行每行包含两个正整数 x,y，表示 x 结点和 y 结点之间有一条直接连接的边（数据保证可以构成树）。

接下来 M 行每行包含两个正整数 a,b，表示询问 a 结点和 b 结点的最近公共祖先。

输出格式
输出包含 M 行，每行包含一个正整数，依次为每一个询问的结果。

输入输出样例：
输入
5 5 4
3 1
2 4
5 1
1 4
2 4
3 2
3 5
1 2
4 5
输出
4
4
1
4
4

代码 (C++)

下面代码中的邻接表是用数组模拟链表的方式实现的，原理和代码模板参考文章 用数组模拟链表的方式实现【带权有向图的邻接表】。

使用 vector 的邻接表会超时。

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
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>

using namespace std;

// ------ 数组维护链表的邻接表，无向无权图 ---------

const int V_SIZE = 5e5 + 1; // 总点数
const int E_SIZE = V_SIZE * 2; // 总边数

int head[V_SIZE]; // head[i] 的值是 ver 下标，相当于链表节点指针
int ver[E_SIZE]; // 边的终点，相当于链表节点的 v 字段
int next_[E_SIZE]; // 相当于链表节点的 next_ 字段

// tot 表示 node 数组(这里是 ver 和 next_)已使用的最右位置，而不是链表长度
int tot;

void init()
{
    tot = 0;
    memset(head, -1, sizeof(head));
    memset(next_, -1, sizeof(head));
}

void add(int x, int y)
{
    ver[++tot] = y;
    next_[tot] = head[x];
    head[x] = tot; // 在表头 x 处插入
}

// --------------------------------------------------

int d[500001], fa[500001][22], parent[500001];

void dfs(int u, int prev)
{
    // 访问从 u 出发的所有边
    for(int i = head[u]; i; i = next_[i])
    {
        int v = ver[i];
        if(v == prev)
            continue;
        d[v] = d[u] + 1;
        parent[v] = u;
        dfs(v, u);
    }
}

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;
}

void get_fa(int N, int K)
{
    // fa[i][j] := 从 i 爬 2 ^ j 步所到点的 id
    // fa[i][0] := 从 i 爬 1 不所到点的 id
    for(int i = 1; i <= N; ++i)
        fa[i][0] = parent[i];
    for(int j = 1; j < K; ++j)
        fa[0][j] = -1;
    for(int j = 1; j < K; ++j)
        for(int i = 1; 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 lca(int x, int y)
{
    if(d[x] < d[y])
        swap(x, y);
    // d[x] >= d[y]
    // 将 x 向上调整直到和 y 一个深度
    int delta = d[x] - d[y];
    while(delta > 0)
    {
        x = fa[x][(int)log2(highbit(delta))];
        delta -= highbit(delta);
    }
    if(x == y)
        return x;
    // int n = d.size();
    int m = log2(highbit(d[x]));
    while(true)
    {
        if(fa[x][0] == fa[y][0])
            break;
        int k = 1;
        while(k <= m)
        {
            if(fa[x][k] == -1 || fa[y][k] == -1)
                break;
            if(fa[x][k] == fa[y][k])
                break;
            ++k;
        }
        x = fa[x][k - 1];
        y = fa[y][k - 1];
    }
    return fa[x][0];
}

int main()
{
    init();

    int N, M, S;
    cin >> N >> M >> S;

    for(int i = 0; i < N - 1; ++i)
    {
        int x, y;
        cin >> x >> y;
        add(x, y);
        add(y, x);
    }

    dfs(S, 0);

    int K = log2(N) + 1;
    get_fa(N, K);

    for(int i = 0; i < M; ++i)
    {
        int a, b;
        cin >> a >> b;
        cout << lca(a, b) << endl;
    }
    return 0;
}

Tarjan 算法

Tarjan 有三大算法，一个是有向图的强连通分量、一个是无向图的双连通分量，这里是最近公共祖先问题。

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

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

Tarjan 算法的核心是 DFS，在 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 的节点。如下图：

利用并查集优化：

当一个节点 v 回溯被标记 2 时， v 的父节点 u 一定是标记为 1 的。且单独构成一个集合。此时把它所在的集合合并到它的父节点 u 所在的集合中，father[v] = u 即可。

在 u 即将回溯时，此时查询 u 所在集合的代表元，就相当于从某个标记为 2 的节点 y 向上走一直到一个开始递归但尚未回溯的节点，其标记为 1，即 lca(u, y)。

因此在 u 即将回溯时，紧接着扫描与 x = u 相关的所有查询 (x, y)，若查询的另一节点 y 被标记为了 2，则 x 和 y 的最近公共祖先为 y 的代表元，lca(x, y) = find(y)。

代码 (C++，模板)

下面是 P3379 【模板】最近公共祖先（LCA） 的代码，在前面我们用树上倍增解决了，这里我们用 Tarjan 算法。

这里图的邻接表还是用数组模拟链表的方式实现；离线处理查询的结构为数组 query 和 query_id；并查集也用数组 father 实现，查询代表元时使用路径压缩，合并 u , v 时直接对 father[v] = u 即可。

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
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <vector>

using namespace std;

// ------ 数组维护链表的邻接表，无向无权图 ---------

const int V_SIZE = 5e5 + 5; // 总点数
const int E_SIZE = V_SIZE * 2; // 总边数

int head[V_SIZE]; // head[i] 的值是 ver 下标，相当于链表节点指针
int ver[E_SIZE]; // 边的终点，相当于链表节点的 v 字段
int next_[E_SIZE]; // 相当于链表节点的 next_ 字段

// tot 表示 node 数组(这里是 ver 和 next_)已使用的最右位置，而不是链表长度
int tot;

void init_graph()
{
    tot = 0;
    memset(head, -1, sizeof(head));
    memset(next_, -1, sizeof(head));
}

void add(int x, int y)
{
    ver[++tot] = y;
    next_[tot] = head[x];
    head[x] = tot; // 在表头 x 处插入
}

// ---- 离线处理所有查询，vector 数组实现邻接表，维护所有的查询及其 id -----

vector<int> query[V_SIZE], query_id[V_SIZE];

void add_query(int x, int y, int i)
{
    query[x].push_back(y);
    query[y].push_back(x);
    query_id[x].push_back(i);
    query_id[y].push_back(i);
}

// ------------- 数组维护并查集 ----------

int father[V_SIZE];

int find(int x)
{
    if(father[x] == x)
        return x;
    else
        return father[x] = find(father[x]); // 路径压缩
}

void init_unionfindset(int N)
{
    for(int i = 0; i <= N; ++i)
        father[i] = i;
}

// -------------- Tarjan 算法 -----------

int visited[V_SIZE];
int ans[V_SIZE];

void init_tarjan()
{
    memset(visited, 0, sizeof(visited));
    memset(ans, -1, sizeof(ans));
}

void tarjan(int u)
{
    visited[u] = 1;
    for(int i = head[u]; i != -1; i = next_[i])
    {
        int v = ver[i];
        if(visited[v] != 0)
            continue;
        tarjan(v);
        // 在并查集中将 v 与 u 合并
        father[v] = u;
    }
    // u 节点准备回溯，标记 2，此时 u 的父节点 fa 一定是标记 1 的
    // 此时在并查集中将 u 代表的集合与 fa 代表的集合合并
    // 此时扫描所有与 u 有关的查询，若另一个节点 v 的标记为 2，则 lca(x, y) = y 的代表元
    int x = u;
    for(int i = 0; i < query[u].size(); ++i)
    {
        int y = query[x][i];
        int id = query_id[x][i];
        if(x == y)
            ans[id] = x;
        if(visited[y] == 2)
        {
            int lca = find(y);
            ans[id] = lca;
        }
    }
    visited[u] = 2;
}

int main()
{
    int N, M, S;
    cin >> N >> M >> S;

    init_graph();
    init_unionfindset(N);
    init_tarjan();

    for(int i = 0; i < N - 1; ++i)
    {
        int x, y;
        cin >> x >> y;
        add(x, y);
        add(y, x);
    }

    for(int i = 0; i < M; ++i)
    {
        int a, b;
        cin >> a >> b;
        add_query(a, b, i);
    }

    tarjan(S);

    for(int i = 0; i < M; ++i)
    {
        cout << ans[i] << endl;
    }
}

例题

给你一些区域列表 regions ，每个列表的第一个区域都包含这个列表内所有其他区域。

很自然地，如果区域 X 包含区域 Y ，那么区域 X 比区域 Y 大。

给定两个区域 region1 和 region2 ，找到同时包含这两个区域的 最小 区域。

如果区域列表中 r1 包含 r2 和 r3 ，那么数据保证 r2 不会包含 r3 。

数据同样保证最小公共区域一定存在。

提示：

1
2
3
2 <= regions.length <= 1e^4
region1 != region2
所有字符串只包含英文字母和空格，且最多只有 20 个字母。

示例 1：
输入：
regions = [[“Earth”,”North America”,”South America”],
[“North America”,”United States”,”Canada”],
[“United States”,”New York”,”Boston”],
[“Canada”,”Ontario”,”Quebec”],
[“South America”,”Brazil”]],
region1 = “Quebec”,
region2 = “New York”
输出：”North America”

算法：向上标记法

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

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

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

之后就可以用向上标记法求 lca 了。

代码 (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
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
class Solution {
public:
    string findSmallestRegion(vector<vector<string>>& regions, string region1, string region2) {
        id = 0;
        node_id = unordered_map<string, int>();
        g = vector<vector<int>>();
        name = vector<string>();
        for(const vector<string>& l: regions)
        {
            if(l.empty()) continue;
            if(node_id.count(l[0]) == 0)
            {
                name.push_back(l[0]);
                node_id[l[0]] = id++;
                g.push_back({});
            }
            int u = node_id[l[0]];
            int n = l.size();
            for(int i = 1; i < n; ++i)
            {
                if(node_id.count(l[i]) == 0)
                {
                    name.push_back(l[i]);
                    node_id[l[i]] = id++;
                    g.push_back({});
                }
                int v = node_id[l[i]];
                g[v].push_back(u);
            }
        }
        if(node_id.count(region1) == 0 || node_id.count(region2) == 0)
            return "-1";

        int N = g.size();
        g.push_back({});
        root = N;
        for(int u = 0; u < N - 1; ++u)
        {
            if(g[u].size() == 0)
                g[u].push_back(root);
        }

        int x = node_id[region1];
        int y = node_id[region2];
        return name[lca(x, y)];
    }

private:
    unordered_map<string, int> node_id;
    vector<string> name;
    int id;
    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;
    }
};

LCA 题目汇总

LCA 的高级应用

在 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