题意
给定一棵$n$个点的无向无根树，每个点有或没有金币。
现在让你从某个节点出发，每次可以收集距离当前点2以内的所有金币，或者移动到一个相邻节点。
问你收集所有金币并返回到出发点最少的步数。
做法
首先考虑固定出发点的情况，答案是什么。显然就是去掉所有叶子节点距离小于等于2的边后剩余边的个数乘以2。
换根DP明显可以解决。
然后我写了1个小时，调了30分钟（实在想不到问题在哪，手画了一下十几个点的错误数据才意识到问题）。
代码写的也是异常丑陋，懒得在递归函数里传一堆参数，所以全改成类的私有变量了。
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:
int collectTheCoins(vector<int>& coins, vector<vector<int>>& edges) {
n = coins.size();
dp.resize(0);
dp.resize(n);
dp2.resize(0);
dp2.resize(n);
G.resize(0);
G.resize(n);
c = coins;
for (const auto& e : edges) {
G[e[0]].push_back(e[1]);
G[e[1]].push_back(e[0]);
}
dfs(0, -1);
dfs2(0, -1);
int ans = 2 * n;
for (int i = 0; i < n; i++) ans = min(ans, dp[i][3] + dp2[i][3]);
return ans;
}
private:
void dfs(int u, int fa) {
for (int v : G[u]) {
if (v == fa) continue;
dfs(v, u);
if (c[v]) dp[u][0]++;
dp[u][1] += dp[v][0];
dp[u][2] += dp[v][1] + dp[v][2];
if (dp[v][1] || dp[v][2]) {
dp[u][3] += dp[v][3] + 2;
}
}
}
void dfs2(int u, int fa) {
for (int v : G[u]) {
if (v == fa) continue;
if (c[u]) dp2[v][0]++;
dp2[v][1] += dp2[u][0] + dp[u][0] - c[v];
dp2[v][2] += dp2[u][1] + dp2[u][2] + dp[u][1] + dp[u][2] - dp[v][0] - dp[v][1] - dp[v][2];
bool ok = false;
if (dp2[u][1] || dp2[u][2] || dp2[u][3]) {
dp2[v][3] += dp2[u][3];
ok = true;
}
if (dp[u][1] + dp[u][2] - dp[v][0] - dp[v][1] - dp[v][2] > 0) {
dp2[v][3] += dp[u][3];
if (dp[v][1] || dp[v][2]) {
dp2[v][3] -= dp[v][3] - 2;
}
ok = true;
}
if (ok) dp2[v][3] += 2;
}
for (int v : G[u]) {
if (v == fa) continue;
dfs2(v, u);
}
}
int n;
vector<array<int, 4>> dp, dp2;
vector<int> c;
vector<vector<int>> G;
};
|
正解
拓扑排序。
对于树中的叶子节点，如果没有金币，直接删除即可。
不断删除后，现在的树的所有叶子节点都有金币，显然我们可以继续删掉两层叶子节点。
答案就是剩下的边数乘以2了。其实就是贪心，并不需要算出从每个点出发的答案具体是什么。