题目链接：https://www.luogu.com.cn/problem/P1352
设dp[i][0/1]，dp[i][0]表示不选第i个职工的最大值，dp[i][1]表示选第i个职工的最大值。
转移：
如果不选第i个职工，那么他的下属可选可不选，即dp[i][0]+=max(dp[j][0],dp[j][1])
如果选第i个职工，那么他的下属一定不能选，即dp[i][1]+=dp[j][0]
AC代码：
1 #include<cstdio> 2 #include<iostream> 3 #include<cstring> 4 using namespace std; 5 const int N=6006; 6 int head[N],vis[N],dp[N][2],r[N]; 7 int n,tot; 8 struct node{ 9 int to,next; 10 }edge[N]; 11 void add(int u,int v){ 12 edge[tot].to=v; 13 edge[tot].next=head[u]; 14 head[u]=tot++; 15 } 16 void DFS(int rt){ 17 dp[rt][1]=r[rt]; 18 for(int i=head[rt];i!=-1;i=edge[i].next){ 19 int v=edge[i].to; 20 DFS(v); 21 dp[rt][0]+=max(dp[v][0],dp[v][1]); 22 dp[rt][1]+=dp[v][0]; 23 } 24 } 25 int main(){ 26 memset(head,-1,sizeof(head)); 27 scanf("%d",&n); 28 for(int i=1;i<=n;i++) scanf("%d",&r[i]); 29 for(int i=1;i<n;i++){ 30 int u,v; 31 scanf("%d%d",&u,&v); 32 add(v,u); 33 vis[u]=1; 34 } 35 for(int i=1;i<=n;i++) 36 if(!vis[i]) { DFS(i); printf("%d",max(dp[i][0],dp[i][1])); return 0;} 37 return 0; 38 }