洛谷 P1352 没有上司的舞会

题目传送门

解题思路:

用f[i][0]表示第i个人没去其本身与所有下属(包括间接)所能获得的最大值,f[i][1]表示第i个人去了其本身与所有下属(包括间接)所能获得的最小值,如果第i个人去了,则它的下属一定没去,如果第一个人没去,则它的下属去或不去皆可.

AC代码:

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<vector>
 4 
 5 using namespace std;
 6 
 7 int n,v[6001],f[6001][2];
 8 vector<int> a[6001];
 9 bool vis[6001];
10 
11 inline void dfs(int root) {
12     f[root][1] = v[root];
13     if(a[root].empty()) return ;
14     for(int i = 0;i < a[root].size(); i++) {
15         dfs(a[root][i]);
16         f[root][1] += f[a[root][i]][0];
17         f[root][0] += max(f[a[root][i]][1],f[a[root][i]][0]); 
18     }
19 }
20 
21 int main() {
22     scanf("%d",&n);
23     for(int i = 1;i <= n; i++)
24         scanf("%d",&v[i]);
25     for(int i = 1;i < n; i++) {
26         int x,y;
27         scanf("%d%d",&x,&y);
28         a[y].push_back(x);
29         vis[x] = 1;
30     }
31     for(int i = 1;i <= n; i++)
32         if(!vis[i]) {
33             dfs(i);
34             printf("%d",max(f[i][0],f[i][1]));
35         }
36     return 0;
37 }