[动态规划](7)树型DP

没有上司的舞会

模板题:285. 没有上司的舞会 - AcWing题库

image-20210707175846617

思维导图:

image-20210707175908620

代码:

```C++

include

include

include

using namespace std; const int N = 6000; int happy[N];//存储每个节点的欢乐值 bool st[N];//记录是否又父节点 //邻接表 int e[N], ne[N], h[N], idx = 0; int n; int f[N][2]; void addnode(int a, int b) { e[idx] = b; ne[idx] = h[a]; h[a] = idx++; } void dfs(int root) { f[root][1] = happy[root];

for (int i = h[root]; i != -1; i = ne[i]) {
    int j = e[i];
    dfs(j);

    f[root][0] += max(f[j][0], f[j][1]);
    f[root][1] += f[j][0];
}
return;

} int main() { cin >> n; memset(h, -1, sizeof h); for (int i = 1; i <= n; i++) cin >> happy[i]; for (int i = 0; i < n - 1; i++) { int a, b; cin >> a >> b; addnode(b, a); st[a] = true; } int root = -1; for (int i = 1; i <= n; i++) if (!st[i]) root = i;

dfs(root);

int res = max(f[root][1], f[root][0]);
cout << res << endl;

return 0;

}

本文链接:

https://nullcode.fun/156.html
1 + 7 =
快来做第一个评论的人吧~