题意：某大学有N个职员，编号为1~N。他们之间有从属关系，也就是说他们的关系就像一棵以校长为根的树，父结点就是子结点的直接上司。现在有个周年庆宴会，宴会每邀请来一个职员都会增加一定的快乐指数Ri，但是呢，如果某个职员的上司来参加舞会了，那么这个职员就无论如何也不肯来参加舞会了。所以，请你编程计算，邀请哪些职员可以使快乐指数最大，求最大的快乐指数。
分析：
-
状态
f[u][0] 表示以u为根节点，且不选u的最大快乐指数。
f[u][1] 表示以u为根节点，且选u的最大快乐指数。 -
转移
如果不选u，对于u的子节点v可以选或不选：f[u][0] += max(f[v][0], f[v][1]);
如果选u，对于u的子节点v只能不选：f[u][0] += f[v][0]; -
目标
ans = max(f[rt][0], f[rt][1])
点击查看代码
#include <algorithm>
#include <cstring>
#include <iostream>
using namespace std;
typedef long long LL;
const int N = 1e6 + 10, INF = 0x3f3f3f3f;
int n, a[N], f[N][2];
struct T {
int v, w, nx;
} g[N];
int h[N], idx;
bool st[N];
void add(int u, int v, int w) {
g[++idx] = {v, w, h[u]}, h[u] = idx;
}
void dfs(int u) {
f[u][0] = 0, f[u][1] = a[u];
for (int i = h[u]; i; i = g[i].nx) {
int v = g[i].v;
dfs(v);
f[u][0] += max(f[v][0], f[v][1]);
f[u][1] += f[v][0];
}
}
int main() {
cin >> n;
for (int i = 1; i <= n; i++)
cin >> a[i];
for (int i = 1, u, v; i <= n; i++) {
cin >> u >> v, st[u] = 1;
add(v, u, 1);
}
int rt = 1;
while (st[rt])
rt++;
dfs(rt);
cout << max(f[rt][0], f[rt][1]);
return 0;
}