生活随笔
收集整理的这篇文章主要介绍了
洛谷 [P1352] 没有上司的舞会
小编觉得挺不错的,现在分享给大家,帮大家做个参考.
树型DP
一个人不能和他的直接上司一起去,那么就分别保存这个人去和不去的最大值
注意转移方程
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
using namespace std;
const int MAXN = 7005;
int n, num[MAXN], dp[MAXN][2], fa[MAXN], head[MAXN], nume, rot;
struct edge{int to, nxt;
}e[MAXN<<1];
void adde(int from, int to) {e[++nume].to = to;e[nume].nxt = head[from];head[from] = nume;
}
void dfs(int rt) {dp[rt][1] = num[rt];for(int i = head[rt]; i; i = e[i].nxt) {int v = e[i].to;if(v == fa[rt]) continue;dfs(v);if(dp[v][1] > dp[v][0]) dp[rt][0] = max(dp[rt][0], dp[rt][0] + dp[v][1]);else dp[rt][0] = max(dp[rt][0], dp[rt][0] + dp[v][0]);dp[rt][1] = max(dp[rt][1], dp[rt][1] + dp[v][0]);}
}
int main() {cin >> n;for(int i = 1; i <= n; i++) cin >> num[i];for(int i = 1; i< n; i++) {int u, v;cin >> u >> v;fa[u] = v;adde(u, v); adde(v, u);}for(int i = 1; i <= n; i++) if(!fa[i]) rot = i;dfs(rot);cout << max(dp[rot][0], dp[rot][1]) << endl;return 0;
}
转载于:https://www.cnblogs.com/Mr-WolframsMgcBox/p/8607449.html
总结
以上是生活随笔为你收集整理的洛谷 [P1352] 没有上司的舞会的全部内容，希望文章能够帮你解决所遇到的问题。
如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。
