题目描述：
有一棵 n 个节点的无向树，节点编号为 0 到 n - 1 ，根节点编号为 0 。给你一个长度为 n - 1 的二维整数数组 edges 表示这棵树，其中 edges[i] = [ai, bi] 表示树中节点 ai 和 bi 有一条边。
同时给你一个长度为 n 下标从 0 开始的整数数组 values ，其中 values[i] 表示第 i 个节点的值。
一开始你的分数为 0 ，每次操作中，你将执行：
- 选择节点
i 。 - 将
values[i] 加入你的分数。 - 将
values[i] 变为 0 。
如果从根节点出发，到任意叶子节点经过的路径上的节点值之和都不等于 0 ，那么我们称这棵树是 健康的 。
你可以对这棵树执行任意次操作，但要求执行完所有操作以后树是 健康的 ，请你返回你可以获得的 最大分数 。
数据范围：
$2\le n \le 2\times 10^4; 1\le values[i] \le 10^9$
题解：
首先每条路径上只保留一个最小的值，剩下的全加到答案中。
正向做法：
使用树形dp，使用 $dp[u][0,1]$ 表示该子树是健康的，所能得到的最大分数，子树不健康所能得到的最大分数。枚举子树 $u$ 的两个状态，看是如何更新的。如果子树 $u$ 是健康的，那么要么所有的孩子都是健康的，然后加上节点 $u$ 的价值，要么就是选择留下 $u$ ，所有的孩子都可以是不健康的。即
$dp[u][0] = \max(\sum dp[v][0] + values[u], \sum dp[v][1])$ .
如果子树 $u$ 是不健康的，说明子树是不健康的，并且 $u$ 节点不留下，加上 $u$ 的价值，即
$dp[u][1] = \sum dp[v][1] + values[u]$ .
需要注意叶子节点，也就是初始化，叶子节点 $g[u].size() = 1 \wedge u \neq 0$ ，叶子节点， $dp[u][0] = 0, dp[u][1] = values[u]$ 。
正难则反：
考虑反向做法，考虑每个子树健康需要留下的最小的权值之和。那么最后的答案就是 $\sum_{i = 0}^n values[i] - dp[0]$ .
那么要保证子树 $u$ 健康，要么留下 $values[u]$ ，要么孩子子树全是健康的。即
$dp[u] = min(values[u], \sum dp[v])$ .
如果是叶子节点，只能 $dp[u] = values[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
| class Solution
{
public:
const static int maxn = 1e5 + 10;
const static int maxm = 1e5 + 10;
const int INF = 0x3f3f3f3f;
long long ans = 0;
vector<vector<int>> g;
vector<int> values;
vector<vector<long long>> dp;
int n;
void dfs(int u, int fa)
{
dp[u][0] = 0;
dp[u][1] = 0;
long long tmp1 = 0;
long long tmp2 = 0;
for (int i = 0; i < g[u].size(); ++i)
{
int v = g[u][i];
if (v == fa)
continue;
dfs(v, u);
tmp1 += dp[v][1];
tmp2 += dp[v][0];
}
if (g[u].size() == 1 && u != 0)
{
dp[u][0] = 0;
dp[u][1] = values[u];
}
else
{
dp[u][0] = max(tmp1, tmp2 + values[u]);
dp[u][1] = tmp1 + values[u];
}
}
long long maximumScoreAfterOperations(vector<vector<int>> &edges, vector<int> &_values)
{
n = edges.size() + 1;
values = _values;
g.resize(n);
dp.resize(n, vector<long long>(2));
for (auto &edge : edges)
{
int u = edge[0];
int v = edge[1];
g[u].emplace_back(v);
g[v].emplace_back(u);
}
dfs(0, -1);
return dp[0][0];
}
};
|
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
| auto optimize_cpp_stdio = []()
{
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cout.tie(nullptr);
return 0;
}();
class Solution
{
public:
const static int maxn = 1e5 + 10;
const static int maxm = 1e5 + 10;
const int INF = 0x3f3f3f3f;
long long ans = 0;
vector<vector<int>> g;
vector<int> values;
vector<long long> dp;
int n;
void dfs(int u, int fa)
{
dp[u] = values[u];
if (g[u].size() == 1 && u != 0)
return;
long long sum = 0;
for (int i = 0; i < g[u].size(); ++i)
{
int v = g[u][i];
if (v == fa)
continue;
dfs(v, u);
sum += dp[v];
}
dp[u] = min(dp[u], sum);
}
long long maximumScoreAfterOperations(vector<vector<int>> &edges, vector<int> &_values)
{
n = edges.size() + 1;
values = _values;
g.resize(n);
dp.resize(n);
for (auto &edge : edges)
{
int u = edge[0];
int v = edge[1];
g[u].emplace_back(v);
g[v].emplace_back(u);
}
long long sum = 0;
for (auto &x : values)
sum += x;
dfs(0, -1);
return sum - dp[0];
}
};
|