题目

某大学有\(n\)个职员，编号为 \(1,2...n\).

他们之间有从属关系，也就是说他们的关系就像一棵以校长为根的树，父结点就是子结点的直接上司。

现在有个周年庆宴会，宴会每邀请来一个职员都会增加一定的快乐指数\(r_i\)，但是呢，如果某个职员的直接上司来参加舞会了，那么这个职员就无论如何也不肯来参加舞会了。

所以，请你编程计算，邀请哪些职员可以使快乐指数最大，求最大的快乐指数.

思路

从根节点开始dfs，dfs到叶节点设置叶节点的状态之后回溯转移。

状态\(f(i,j)\)表示以\(i\)点为根的子树，职员\(i\)来与不来能获得的最大快乐指数，其中\(j=0\)代表不来，\(j=1\)代表来。

叶节点的状态设置为\(f(i,0)=0,f(i,1)=a[i]\)，其中\(a[i]\)为员工\(i\)能增加的快乐指数。

对于所有子节点都dfs过的点，其转移方程为：

\(f(i,1)=a[i] + \sum f(j,0)\)，\(f(i,0)=\sum max\{f(j,0),f(j,1)\}\)

最终的答案就是根节点\(p\)参加与不参加的最大值。

代码

#include <iostream>
#include <cstring>

const int N = 10005;

struct EDGE {
    int v, ne;
} e[N];

int h[N], tot;
int a[N], in[N], dp[N][2];

void add(int u, int v) {
    e[tot].v = v;
    e[tot].ne = h[u];
    h[u] = tot++;
}

void dfs(int p) {
    dp[p][1] = a[p];
    if (h[p] == -1) {
        return;
    }
    for (int i = h[p]; i != -1; i = e[i].ne) {
        int v = e[i].v;
        dfs(v);
        dp[p][1] += dp[v][0];
        dp[p][0] += std::max(dp[v][0], dp[v][1]);
    }
}

void solve() {
    memset(h, -1, sizeof h);
    int n;
    std::cin >> n;
    for (int i = 1; i <= n; i++) {
        std::cin >> a[i];
    }
    for (int i = 0; i < n - 1; i++) {
        int l, k;
        std::cin >> l >> k;
        add(k, l);
        in[l]++;
    }
    int p;
    for (p = 1; p <= n; p++) {
        if (in[p] == 0) break;
    }
    dfs(p);
    int ans = std::max(dp[p][0], dp[p][1]);
    std::cout << ans << std::endl;
}

int main() {
    solve();
    return 0;
}