题目描述 Description Ural大学有N个职员，编号为1~N。他们有从属关系，也就是说他们的关系就像一棵以校长为根的树，父结点就是子结点的直接上司。每个职员有一个快乐指数。现在有个周年庆宴会，要求与会职员的快乐指数最大。但是，没有职员愿和直接上司一起与会。
输入描述 Input Description
第一行一个整数N。(1<=N<=6000) 接下来N行，第i+1行表示i号职员的快乐指数Ri。(-128<=Ri<=127) 接下来N-1行，每行输入一对整数L,K。表示K是L的直接上司。 最后一行输入0,0。
输出描述 Output Description
输出最大的快乐指数。
样例输入 Sample Input
7 1 1 1 1 1 1 1 1 3 2 3 6 4 7 4 4 5 3 5 0 0
样例输出 Sample Output
5
数据范围及提示 Data Size & Hint
各个测试点1s
一个树形DP的题啦！
#include <iostream> #include <cstdio> using namespace std; struct Edge { int f, t; }es[6010]; int tot = 1, first[6010], nxt[6010], num[6010], fa[6010], dp[6010][5]; void build(int f, int t) { es[++tot] = (Edge){f, t}; nxt[tot] = first[f]; first[f] = tot; } void dfs(int u) { dp[u][1] += num[u]; for(int i = first[u]; i; i = nxt[i]) { int v = es[i].t; dfs(v); dp[u][0] += max(dp[v][0], dp[v][1]); dp[u][1] += dp[v][0]; } } int main() { int n; scanf("%d", &n); for(int i = 1; i <= n; i++) scanf("%d", &num[i]), fa[i] = i; int f, t; for(int i = 1; i <= n; i++) { scanf("%d%d", &t, &f); if(t && f) build(f, t), fa[t] = f; } int rt; for(int i = 1; i <= n; i++) if(fa[i] == i) dfs(i), rt = i; printf("%d", max(dp[rt][1], dp[rt][0])); return 0; }转载于:https://www.cnblogs.com/Loi-Vampire/p/6017034.html
