原题链接

对于每一个节点来说，只有两种情况，就是出席此次宴会和不出席此次宴会，因此储存节点状态可以使用u[N][2]来实现。这样，对于每个节点来说，两种情况分别如下：

  1. 若该节点选择不参加宴会，那么他的所有子节点可以参加也可以不参加，因此有$u[root][0]=\sum \max{u[s_i][0],u[s_i][1]}$
  2. 若该节点参加宴会，那么他所有的子节点必须不参加，因此有$u[root][1]=\sum u[s_i][0]+happy[root]$

实现代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#include <bits/stdc++.h>
using namespace std;
const int N = 6001;
int happy[N], u[N][2];
int h[N], idx, ne[N], e[N];
int n;
bool has_father[N];
void add(int k, int l) {
    e[idx] = l, ne[idx] = h[k], h[k] = idx++;
}

void dfs(int root) {
    u[root][1] = happy[root];
    if(h[root] == -1) {
        u[root][0] = 0;
        return;
    }
    for(int k = h[root]; k != -1; k = ne[k]) {
        dfs(e[k]);
        u[root][0] += max(u[e[k]][0], u[e[k]][1]);
        u[root][1] += u[e[k]][0];
    }

}

int main() {
    queue<int> q;
    scanf("%d", &n);
    for(int i = 1; i <= n; ++i) scanf("%d", &happy[i]);
    memset(h, -1, sizeof h);
    for(int i = 1; i < n; ++i) {
        int k, l;
        scanf("%d%d", &l, &k);
        add(k, l); // k是l的上司
        has_father[l] = true;
    }
    int i = 1;
    for(; i <= n; ++i) if(has_father[i]== false) break;
    dfs(i);
    printf("%d", max(u[i][0], u[i][1]));
    return 0;
}