有个公司要举行一场晚会。
为了能玩得开心，公司领导决定：如果邀请了某个人，那么一定不会邀请他的上司
（上司的上司，上司的上司的上司……都可以邀请）。
每个参加晚会的人都能为晚会增添一些气氛，求一个邀请方案，使气氛值的和最大。

Input

第1行一个整数N（1<=N<=6000）表示公司的人数。
接下来N行每行一个整数。第i行的数表示第i个人的气氛值x(-128<=x<=127)。
接下来每行两个整数L，K。表示第K个人是第L个人的上司。
输入以0 0结束。

Output

一个数，最大的气氛值和。

Sample Input

Sample output

解题思路

【树形DP经典题型】dp【i】【0】dp【i】【1】表示从i取或者不取最大值。

dp【i】【0】+=max（dp【son】【1】，dp【son】【0】）；

dp【i】【1】+=max（dp【son】【0】）；

Hint

#include<bits/stdc++.h>
using namespace std;
int n,cnt,ans;
int s[1000000],v[1000000];
vector<int> tot[100000];
int dp[100000][10];
void f(int x){
dp[x][0]=0;
dp[x][1]=s[x];
for(int i=0;i<tot[x].size();i++){
int y=tot[x][i];
f(y);
dp[x][0]+=max(dp[y][0],dp[y][1]);
dp[x][1]+=dp[y][0];
}
}
int main(){
cin>>n;
for(int i=1;i<=n;i++){
cin>>s[i];
}
for(int i=1;i<=n-1;i++){
int a,b;
cin>>a>>b;
tot[b].push_back(a);
v[a]=1;
}
for(int i=1;i<=n;i++){
if(!v[i]){
cnt=i;
break;
}
}
f(cnt);
ans=max(dp[cnt][0],dp[cnt][1]);
cout<<ans;
return 0;
}

【题解】没有上司的晚会 Description 解题思路 Hint