AcWing 285. 没有上司的舞会
原题链接
简单
作者:
geats兔
,
2024-04-01 21:09:26
,
所有人可见
,
阅读 1
#include<iostream>
#include<cstring>
using namespace std;
const int N=6010;
bool st[N];
int h[N],e[N],w[N],ne[N],idx;
int f[N][2];
int n;
int res;
void add(int a,int b){
e[idx]=b;ne[idx]=h[a];h[a]=idx++;
}
void dfs(int u,int father){
f[u][1]=w[u];
for(int i=h[u];~i;i=ne[i]){
int j=e[i];
if(j==father) continue;
dfs(j,u);
f[u][1]+=f[j][0];
f[u][0]+=max(f[j][0],f[j][1]);
}
}
int main(){
cin>>n;
memset(h,-1,sizeof h);
for (int i = 1; i <= n; i ++ )
cin>>w[i];
for (int i = 0; i < n-1; i ++){
int a,b;
cin>>a>>b;
st[a]=true;
add(b,a);
}
int root=1;
while(st[root]) root++;
dfs(root,-1);
res=max(f[root][0],f[root][1]);
cout<<res<<endl;
return 0;
}