没有上司的舞会

题目描述

某大学有 $n$ 个职员，编号为 $1\ldots n$。

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

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

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

输入格式

输入的第一行是一个整数 $n$。

第 $2$ 到第 $(n + 1)$ 行，每行一个整数，第 $(i+1)$ 行的整数表示 $i$ 号职员的快乐指数 $r_i$。

第 $(n + 2)$ 到第 $2n$ 行，每行输入一对整数 $l, k$，代表 $k$ 是 $l$ 的直接上司。

输出格式

输出一行一个整数代表最大的快乐指数。

样例 #1

样例输入 #1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
7
1
1
1
1
1
1
1
1 3
2 3
6 4
7 4
4 5
3 5

样例输出 #1

1
5

提示

数据规模与约定

对于 $100\%$ 的数据，保证 $1\leq n \leq 6 \times 10^3$，$-128 \leq r_i\leq 127$，$1 \leq l, k \leq n$，且给出的关系一定是一棵树。

解题思路

化整为零，先考虑子问题；

一棵树的最大值可由它的子树转移而来，且根节点的选择与否直接影响到子树的最大值，所以需要记录一个状态$0$表示不选根节点，$1$表示选择根节点；

$f[i][j]$表示以$i$为根的子树，$j$可以取$0$或者$1$，分别表示选择节点$i$的与否，其属性存储最大值。

我们需要从叶子节点开始，逐步转移到根节点，这里采用 DFS 进行搜素。

AC代码

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
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 6010;

int happy[N];

int n;

int h[N],e[N],ne[N],idx;

int f[N][2];

void add(int x,int y) {
    e[idx] = y,ne[idx] = h[x],h[x] = idx ++;
}

int d[N];

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

int main() {
    scanf("%d", &n);
    for(int i = 1; i <= n; ++ i) h[i] = -1;
    for(int i = 1; i <= n; ++ i)
        scanf("%d", &happy[i]);
    int a,b;
    for(int i = 1; i < n; ++ i) {
        scanf("%d%d", &a,&b);
        add(b,a);
        ++d[a];
    }
    int root;
    for(int i = 1; i <= n; ++ i)
        if(!d[i]) {
            root = i;
            break;
        }
    dfs(root);
    cout << max(f[root][0],f[root][1]) << endl;
    return 0;
}