算法动态规划

二次扫描与换根DP

字数统计: 3.6k字   |   阅读时长: 16分
, , ,

摘要: 无根树上的树形DP，二次扫描与换根的处理方法

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

在文章 树形DP 中，我们简要介绍了树形 DP 的思想，以及列举了很多可以解决的问题。

在有的问题中，树形 DP 状态设计要分为 dpup 和 dpdown 并且转移的时候分成两步 dfs 来做(有时通过一些推导也可以变成一趟dfs)，称为二次扫描与换根法。本文以力扣 310 和 acwing 上的一道题来看一下这种二次扫描与换根法的处理方式。

$1 不定根树形 DP

不定根的树形 DP 问题的特点是给定树形结构之后，需要将每个点都视为根进行一轮树形 DP，最终得到结果。这个过程一般通过两次扫描来解决。

二次扫描与换根法

树形 DP 二次扫描的过程中，一般需要 3 个 dp 数组。定义如下：

1
2
3
4
状态定义：
dpdown[u] := 以 root 为根的有根树上 u 子树的结果
dpup[u] := 以 root 为根的有根树上 u 向其父节点走并且此后不返回 u 的情况，可以取得的结果。
dp[u] := 整棵树以 u 为根的结果

在用二次扫描与换根法解决不定根树形 DP 的过程中：

  • 第一次扫描时任选一个点为根，在有根树上执行一次树形 DP，也就是在回溯时发生的，以自底向上的状态转移推导 dpdown。
  • 第二次扫描时从刚才的根出发，对整棵树 DFS，在节点 u 上，在递归 u 的各个子节点 v 之前，以进行自顶向下的状态转移推导 dpup，计算换根后的解 dp。

两次扫描围绕着 dp, dpdown, dpup 进行推导和更新，具体的转移方程需要看具体的问题。

$2 题目

310. 最小高度树

树是一个无向图，其中任何两个顶点只通过一条路径连接。 换句话说，一个任何没有简单环路的连通图都是一棵树。

给你一棵包含 n 个节点的树，标记为 0 到 n - 1 。给定数字 n 和一个有 n - 1 条无向边的 edges 列表（每一个边都是一对标签），其中 edges[i] = [ai, bi] 表示树中节点 ai 和 bi 之间存在一条无向边。

可选择树中任何一个节点作为根。当选择节点 x 作为根节点时，设结果树的高度为 h 。在所有可能的树中，具有最小高度的树（即，min(h)）被称为 最小高度树 。

请你找到所有的 最小高度树 并按 任意顺序 返回它们的根节点标签列表。

树的 高度 是指根节点和叶子节点之间最长向下路径上边的数量。

提示：

1
2
3
4
5
6
1 <= n <= 2 * 1e4
edges.length == n - 1
0 <= ai, bi < n
ai != bi
所有 (ai, bi) 互不相同
给定的输入 保证 是一棵树，并且 不会有重复的边

示例 1：
输入：n = 4, edges = [[1,0],[1,2],[1,3]]
输出：[1]
解释：如图所示，当根是标签为 1 的节点时，树的高度是 1 ，这是唯一的最小高度树。

示例 2：
输入：n = 6, edges = [[3,0],[3,1],[3,2],[3,4],[5,4]]
输出：[3,4]

算法1：树形DP + 二次扫描

考虑以 u 为根的子树，与点 u 形成最远距离的点为 v，有两种情况：

(1) 一种是 v 在 u 的子树上。
(2) 另一种是 v 在整棵树去掉 u 子树后的部分。

因此从点 u 要分为从 u 往下走和从 u 网上走两步。

  • 往下走就是树高 dpdown[u][s] = dp[u][s] (s = 0,1) := 树上最长链的状态：
1
2
3
4
5
6
7
8
9
10
dpdowm[u][0] = dp[u][0];
dpdowm[u][1] = dp[u][1];
其中
dp[u][0] := 以 u 为根且包含 u 的最长链
dp[u][1] := 以 u 为根且包含 u 的次长链
用 dp[u][0], dp[u][0] + dp[u][1] - 1 更新 ans
dp[u][0] = 1                   u为叶子节点
         = max(dp[v][0]) + 1   v为u的子节点
dp[u][1] = -INF                       u为叶子节点
         = second_max(dp[v][0]) + 1   v为u的子节点
  • 往上走 dpup[u] := 从上面到 u 的最长：
1
2
3
4
5
6
u 为根
dpup[u] = 1  
u 不为根，记其父节点为 fa
dpup[u] = max(dpdown[u][0] + 1,  (u 不在经过 fa 的最长链上)
              dpdown[u][1] + 1,  (u 在经过 fa 的最长链上)
              dpup[fa] + 1)

对于 u 而言，最大距离就是 max(dpup[u], dpdown[u][0])。

状态转移分为 dpup 和 dpdown 并且分成两步 dfs 来做，很多树形DP问题是这么处理的。

判断 u 在 fa 的最长链上的方法为：dpdown[u] + 1 = dpdown[fa]。

代码 (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
class Solution {
public:
    vector<int> findMinHeightTrees(int n, vector<vector<int>>& edges) {
        vector<vector<int> > g(n); // 邻接表
        for(vector<int> &edge: edges)
        {
            g[edge[0]].push_back(edge[1]);
            g[edge[1]].push_back(edge[0]);
        }
        vector<int> max_height(n, 0), t(n, 0);
        // 第一次DFS记录每个结点在作为子树根结点的最大高度。
        dfs_1(0, -1, max_height, g);
        // 第二次DFS补全每个结点作为总根结点的最大高度，差距就在于需要统计上从父结点传递过来的子树分支。
        dfs_2(0, -1, max_height, t, g);

        int min_ans = n;
        vector<int> ans;
        for(int i = 0; i < n; ++i)
        {
            if(min_ans > max_height[i])
            {
                min_ans = max_height[i];
                ans.clear();
                ans.push_back(i);
            }
            else if(min_ans == max_height[i])
                ans.push_back(i);
        }
        return ans;
    }

private:
    void dfs_1(int u, int fa, vector<int>& max_height, vector<vector<int> >& g)
    {
        max_height[u] = 0;
        for(auto &v: g[u])
        {
            if(v == fa) continue;
            dfs_1(v, u, max_height, g);
            max_height[u] = max(max_height[u], max_height[v] + 1);
        }
    }

    void dfs_2(int u, int fa, vector<int>& max_height, vector<int>& t, vector<vector<int> >& g)
    {
        max_height[u] = max(max_height[u], t[u]);
        int max_1 = 0, max_2 = 0; // 这里需要最大高度和次大高度
        for(auto &v: g[u])
        {
            if(v == fa) continue;
            if(max_1 < max_height[v] + 1)
            {
                max_2 = max_1;
                max_1 = max_height[v] + 1;
            }
            else if(max_2 < max_height[v] + 1)
                max_2 = max_height[v] + 1;
        }
        for(auto &v: g[u])
        {
            if(v == fa) continue;
            if (max_1 == max_height[v] + 1) {
                // u 在 fa 的最长链上
                t[v] = max(t[u], max_2) + 1;
                dfs_2(v, u, max_height, t, g);
            }
            else {
                t[v] = max(t[u], max_1) + 1;
                dfs_2(v, u, max_height, t, g);
            }
        }
    }
};

算法2：贪心+拓扑排序

每次总是删除入度最少的点，因为树是无向无环图，删除了它们以后，与之相连的结点的入度也相应地减少 1，直到最后剩下 1 个结点或者 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
49
50
51
52
class Solution {
public:
    vector<int> findMinHeightTrees(int n, vector<vector<int>>& edges) {
        if(n == 1) return vector<int>(1, 0);
        vector<vector<int> > g(n); // 邻接表
        vector<int> indegrees(n, 0);
        for(vector<int> &edge: edges)
        {
            g[edge[0]].push_back(edge[1]);
            g[edge[1]].push_back(edge[0]);
            ++indegrees[edge[0]];
            ++indegrees[edge[1]];
        }

        queue<int> q;
        for(int i = 0; i < n; ++i)
            if(indegrees[i] == 1)
                q.push(i);

        vector<int> level_nodes;
        vector<int> result;
        int i = 0;
        while(!q.empty())
        {
            if(i == n - 1 || i == n - 2)
            {
                while(!q.empty())
                {
                    result.push_back(q.front());
                    q.pop();
                }
            }
            level_nodes.clear();
            while(!q.empty())
            {
                level_nodes.push_back(q.front());
                q.pop();
                ++i;
            }
            for(int node: level_nodes)
            {
                for(int son: g[node])
                {
                    --indegrees[son];
                    if(indegrees[son] == 1)
                        q.push(son);
                }
            }
        }
        return result;
    }
};

834. 树中距离之和

给定一个无向、连通的树。树中有 n 个标记为 0…n-1 的节点以及 n-1 条边 。

给定整数 n 和数组 edges ， edges[i] = [ai, bi]表示树中的节点 ai 和 bi 之间有一条边。

返回长度为 n 的数组 answer ，其中 answer[i] 是树中第 i 个节点与所有其他节点之间的距离之和。

提示:

1
2
3
4
5
6
1 <= n <= 3 * 1e4
edges.length == n - 1
edges[i].length == 2
0 <= ai, bi < n
ai != bi
给定的输入保证为有效的树

示例 1:
输入: n = 6, edges = [[0,1],[0,2],[2,3],[2,4],[2,5]]
输出: [8,12,6,10,10,10]
解释: 树如图所示。
我们可以计算出 dist(0,1) + dist(0,2) + dist(0,3) + dist(0,4) + dist(0,5)
也就是 1 + 1 + 2 + 2 + 2 = 8。 因此，answer[0] = 8，以此类推。

示例 2:
输入: n = 1, edges = []
输出: [0]

示例 3:
输入: n = 2, edges = [[1,0]]
输出: [1,1]

算法：树形DP + 二次扫描

每个节点的答案分为三部分：left、right、father。

因此这是包含 dpup 和 dpdown 两部分的树形 DP：

  • 第一次 dfs 求 dpdowm，也就是 left、right 部分对答案的贡献，并记录子树节点个数，父节点等信息。
  • 第二次 dfs 求 dpup，也就是 father 部分对答案的贡献，并整合结果。

代码 (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
class Solution {
public:
    vector<int> sumOfDistancesInTree(int N, vector<vector<int>>& edges) {
        vector<vector<int> > g(N);
        for(const vector<int>& edge: edges)
        {
            g[edge[0]].push_back(edge[1]);
            g[edge[1]].push_back(edge[0]);
        }
        vector<bool> visited(N, false);
        vector<int> father(N, -1);
        vector<int> result(N);
        vector<int> cnts(N);
        _postOrder(g, 0, visited, father, result, cnts);
        visited.assign(N, false);
        _preOrder(g, 0, visited, father, result, cnts);
        return result;
    }

private:
    // 每个节点的答案分 left, right ,father 三部分
    // _postOrder 负责 left 和 right 两部分
    void _postOrder(const vector<vector<int> >& g, int cur, vector<bool>& visited,
            vector<int>& father, vector<int>& result, vector<int>& cnts)
    {
        // 返回值：子树的节点个数
        // len: 子树的根 root 到树中所有节点的距离值和
        // cnt: 子树的节点个数
        visited[cur] = true;
        int cnt = 0;
        int len = 0;
        for(int son: g[cur])
        {
            if(visited[son]) continue;
            father[son] = cur;
            _postOrder(g, son, visited, father, result, cnts);
            cnt += cnts[son];
            len += cnts[son] + result[son];
        }
        cnts[cur] = cnt + 1;
        result[cur] = len;
    }

    // _preOrder 负责 father 的部分
    void _preOrder(const vector<vector<int> >& g, int cur, vector<bool>& visited,
            const vector<int>& father, vector<int>& result, const vector<int>& cnts)
    {
        // father_len := 父节点的三部分总和
        visited[cur] = true;
        if(father[cur] != -1)
            result[cur] += (result[father[cur]] - cnts[cur] - result[cur]) + (cnts[0] - cnts[cur]);
        for(int son: g[cur])
        {
            if(visited[son]) continue;
            _preOrder(g, son, visited, father, result, cnts);
        }
    }
};

287. 积蓄程度

有一个树形的水系，由 N-1 条河道和 N 个交叉点组成。

我们可以把交叉点看作树中的节点，编号为 1~N，河道则看作树中的无向边。

每条河道都有一个容量，连接 x 与 y 的河道的容量记为 c(x,y)。

河道中单位时间流过的水量不能超过河道的容量。

有一个节点是整个水系的发源地，可以源源不断地流出水，我们称之为源点。

除了源点之外，树中所有度数为 1 的节点都是入海口，可以吸收无限多的水，我们称之为汇点。

也就是说，水系中的水从源点出发，沿着每条河道，最终流向各个汇点。

在整个水系稳定时，每条河道中的水都以单位时间固定的水量流向固定的方向。

除源点和汇点之外，其余各点不贮存水，也就是流入该点的河道水量之和等于从该点流出的河道水量之和。

整个水系的流量就定义为源点单位时间发出的水量。

在流量不超过河道容量的前提下，求哪个点作为源点时，整个水系的流量最大，输出这个最大值。

1
2
3
4
5
6
7
8
9
10
11
12
13
输入格式：
输入第一行包含整数 T，表示共有 T 组测试数据。
每组测试数据，第一行包含整数 N。
接下来 N−1 行，每行包含三个整数 x,y,z，表示 x，y 之间存在河道，且河道容量为 z。
节点编号从 1 开始。

输出格式
每组数据输出一个结果，每个结果占一行。


数据范围
N<=2e5
数据保证结果不超过 2^31−1。

输入样例：
1
5
1 2 11
1 4 13
3 4 5
4 5 10
输出样例：
26

树形DP + 二次扫描

1
2
3
4
5
6
7
8
9
10
11
12
13
14
dp[u] := 整棵树以 u 为根，从 u 向外发出的最大流量
dp[u] = dpup[u] + dpdown[u]
dpdown[u] := 整棵树以 root 为根，u 流向其子树的流量之和
dpup[u] := 整棵树以 root 为根，u 沿着其父节点进而流向其它节点的流量之和

初始化
dp[root] = dpdown[root]
dpup[root] = 0
dpdown[u] = 0   u 为叶子

dpdown[u] = sum(min(dpdown[v], c[u][v])) u 为非叶子, v 的度 > 1
          = c[u][v]                      u 为非叶子, v 的度 = 1
dpup[u] = min(dp[fa] - min(dpdown[u], c[fa][u]), c[fa][u]) u != root, fa 的度 > 1
        = c[fa][u]                                         u != root, fa 的度 = 1(其实就是 fa 为 root)

代码 (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
#include <vector>
#include <iostream>

using namespace std;

struct EdgeTo
{
    int v;
    int w;
    EdgeTo(int v, int w):v(v),w(w){}
};

void dfs1(const vector<vector<EdgeTo>>& g, int u, int fa, vector<int>& dpdown, vector<int>& degrees)
{
    for(const EdgeTo &son: g[u])
    {
        int v = son.v;
        ++degrees[u];
        if(v == fa)
            continue;
        dfs1(g, v, u, dpdown, degrees);
        if(degrees[v] > 1)
            dpdown[u] += min(son.w, dpdown[v]);
        else
            dpdown[u] += son.w;
    }
}

void dfs2(const vector<vector<EdgeTo>>& g, int u, int fa, const vector<int>& dpdown, vector<int>& dpup, int& ans, const vector<int>& degrees)
{
    ans = max(ans, dpdown[u] + dpup[u]);
    for(const EdgeTo &son: g[u])
    {
        int v = son.v;
        if(v == fa)
            continue;
        if(degrees[u] > 1)
            dpup[v] = min(dpdown[u] + dpup[u] - min(dpdown[v], son.w), son.w);
        else
            dpup[v] = son.w;
        dfs2(g, v, u, dpdown, dpup, ans, degrees);
    }
}

void solve()
{
    int N;
    cin >> N;
    vector<vector<EdgeTo>> g(N + 1);
    for(int i = 1; i <= N -1; ++i)
    {
        int u, v, w;
        cin >> u >> v >> w;
        g[u].emplace_back(v, w);
        g[v].emplace_back(u, w);
    }
    int root = 1;
    vector<int> dpdown(N + 1);
    vector<int> degrees(N + 1);
    dfs1(g, root, -1, dpdown, degrees);
    vector<int> dpup(N + 1);
    int ans = 0;
    dfs2(g, root, -1, dpdown, dpup, ans, degrees);
    cout << ans << endl;
}

int main()
{
    int T;
    cin >> T;
    for(int i = 1; i <= T; ++i)
        solve();
}
Share