题意
给你一棵树，你可以去掉m个点$(m\in [0,n])$，然后计算剩余结点的贡献。 每个结点的贡献为它本身的价值加上它所有直接相连儿子的价值。 当然你需要合理安排删去的i个结点使贡献最小化。输出每个i对应的贡献值。
思路
有树、节点、贡献，得出树形dp。
设f[i][j]表示以i为根节点的子树中留下j个节点的最小贡献。 题意表示，必须杀掉父节点才能杀掉子节点，所以父节点是否存活也很关键。即： f[0][i][j]表示删掉i后留下j个节点的最小贡献。 f[1][i][j]表示保留i后留下j-1个节点的最小贡献。
$状态转移都是从子节点转移到父节点：$ $$f[0][u][j+k]=min(f[0][u][j+k],f[0][u][j]+min(f[0][v][k],f[1][v][k]))$$ $$f[1][u][j+k]=min(f[1][u][j+k],f[1][u][j]+min(f[0][v][k],f[1][v][k]+val[v]))$$
第二个为什么要加上val[v]，因为题意说对于一个节点的贡献，是自己加上所有儿子的权值。
上面的状态转移直接背包即可。
Code
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
| ##include "bits/stdc++.h"
using namespace std;
typedef long long ll;
const int N = 5e3 + 10;
ll val[N];
int siz[N];
ll f[2][N][N];
vector<int> g[N];
void dfs(int u) {
siz[u] = 1;
f[1][u][1] = val[u];
f[0][u][0] = 0;
for(auto v : g[u]) {
dfs(v);
for(int j = siz[u];j >= 0; j--) {
for(int k = siz[v];k >= 0; k--) {
f[0][u][j + k] = min(f[0][u][j + k], f[0][u][j] + min(f[0][v][k], f[1][v][k]));
f[1][u][j + k] = min(f[1][u][j + k], f[1][u][j] + min(f[0][v][k], f[1][v][k] + val[v]));
}
}
siz[u] += siz[v];
}
}
void solve() {
int _; cin >> _;
while(_--) {
int n; cin >> n;
for(int i = 0;i <= n; i++) {
g[i].clear();
for(int j = 0;j <= n; j++) {
f[0][i][j] = f[1][i][j] = 1e18;
}
}
for(int i = 2;i <= n; i++) {
int u; cin >> u;
g[u].eb(i);
}
for(int i = 1;i <= n; i++) cin >> val[i];
dfs(1);
for(int i = n;i >= 0; i--) {
cout << min(f[0][1][i], f[1][1][i]) << " \n"[i == 0];
}
}
}
signed main() {
solve();
}
|
本文作者：jujimeizuo
本文地址： https://blog.jujimeizuo.cn/2021/03/22/2020-icpc-nanjing-monster-hunter/
本博客所有文章除特别声明外，均采用 CC BY-SA 3.0 协议。转载请注明出处！