题解 P1352 【没有上司的舞会】

· · 题解

这个数据不强，它改一下描述上司关系的顺序应该就过不了了。（不要问我我怎么猜到的数据有问题）

方程：上司来最好心情值=上司心情+每个直接下属不来的最好心情值；

上司不来最好心情值=每个直接下属来与不来的最好心情值的优值。

#include<cstdio>
#include<iostream>
using namespace std;
int n,a,b,ans,f[9000][2];
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%d",&f[i][1]);
ans=f[1][1];
for(int i=1;i<n;i++){
scanf("%d%d",&a,&b);
f[b][1]+=f[a][0];//核心代码
f[b][0]+=max(f[a][0],f[a][1]);
ans=max(ans,f[b][1]);
ans=max(ans,f[b][0]);
}
printf("%d",ans);
}