二次扫描与换根DP

  |  

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

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


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

在有的问题中,树形 DP 状态设计要分为 dpupdpdown 并且转移的时候分成两步 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
dpdown[u][0] = dp[u][0];
dpdown[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])

状态转移分为 dpupdpdown 并且分成两步 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 求 dpdown,也就是 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