题目#

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

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

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

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

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

题解#

设f[u][1/0]代表以u为子树选/不选u能获得的最大价值然后分类即可

错误#

1.add函数nxt写错 2.f[u][1]要加上r

代码#

1
#include<bits/stdc++.h>
2

3
using namespace std;
4

5
const int N = 6e3 + 100;
6

7
int read()
8
{
9
  int f = 1, x = 0;
10
  char ch = getchar();
11
  while(ch < '0' || ch > '9')
12
  {
13
    if(ch == '-') f = -1;
14
    ch = getchar();
15
  }
16

17
  while(ch >= '0' && ch <= '9')
18
  {
19
    x = x * 10 + ch - '0';
20
    ch = getchar();
21
  }
22
  return f * x;
23
}
24

25
int head[N], to[N], nxt[N], cnt = 1;
26
int n;
27
int r[N], in_edge[N], root;
28
int f[N][2];
29

30

31
void add(int x, int y)
32
{
33
  to[++cnt] = y;
34
  nxt[cnt] = head[x];
35
  head[x] = cnt;
36
}
37

38
void dfs(int u)
39
{
40
  for(int i = head[u]; i; i = nxt[i])
41
  {
42
    int v = to[i];
43
    dfs(v);
44
    f[u][1] += f[v][0];
45
    f[u][0] += max(f[v][0], f[v][1]);
46
  }
47
  f[u][1] += r[u];
48
  if(f[u][1] == 0 && f[u][0] == 0)
49
  {
50
    f[u][1] = r[u];
51
  }
52
  return;
53
}
54

55
int main()
56
{
57
  n = read();
58

59
  for(int i = 1;i <= n;i++)
60
  {
61
    r[i] = read();
62
  }
63
  int x, y;
64
  for(int i = 1;i < n;i++)
65
  {
66
    x = read(), y = read();
67
    add(y, x);
68
    in_edge[x] ++;
69
  }
70

71
  for(int i = 1;i <= n;i++)
72
  {
73
    if(in_edge[i] == 0)
74
    {
75
      root = i;
76
      break;
77
    }
78
  }
79

80
  dfs(root);
81

82
  printf("%d", max(f[root][1], f[root][0]));
83
  return 0;
84
}