[luoguP1352] 没有上司的舞会（DP）

传送门

树上的dp，从底向上dp就行。

设dp[u][0]表示不选节点 u 的最大值，dp[u][1]表示选节点 u 的最大值。

则状态转移方程为：

dp[u][0] = ∑max(dp[v][1], dp[v][0])

dp[u][1] = ∑dp[v][0] + val[u]

（节点v是节点u的孩子）

——代码

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <iostream>
 4 #define MAXN 12001
 5 
 6 using namespace std;
 7 
 8 int n, cnt;
 9 int head[MAXN], to[MAXN], next[MAXN], val[MAXN], f[MAXN], r[MAXN], dp[MAXN][2];
10 
11 inline void add(int x, int y)
12 {
13     to[cnt] = y;
14     next[cnt] = head[x];
15     head[x] = cnt++;
16 }
17 
18 inline void dfs(int u)
19 {
20     int i, v;
21     dp[u][1] = val[u];
22     for(i = head[u]; i != -1; i = next[i])
23     {
24         v = to[i];
25         if(v != f[u])
26         {
27             f[v] = u;
28             dfs(v);
29             dp[u][0] += max(dp[v][1], dp[v][0]);
30             dp[u][1] += dp[v][0];
31         }
32     }
33 }
34 
35 int main()
36 {
37     int i, x, y, pos;
38     scanf("%d", &n);
39     memset(head, -1, sizeof(head));
40     for(i = 1; i <= n; i++) scanf("%d", &val[i]);
41     for(i = 1; i < n; i++)
42     {
43         scanf("%d %d", &x, &y);
44         add(y, x);
45         r[x]++;
46     }
47     for(i = 1; i <= n; i++)
48         if(!r[i])
49         {
50             pos = i;
51             break;
52         }
53     dfs(pos);
54     printf("%d", max(dp[pos][0], dp[pos][1]));
55     return 0;
56 }

View Code