AcWing 1220. 生命之树
原题链接
中等
作者:
geats兔
,
2024-04-01 23:46:42
,
所有人可见
,
阅读 1
#include<iostream>
#include<cstring>
using namespace std;
const int N=1e5+10;
typedef long long ll;
int h[N],e[2*N],ne[2*N],idx;
int w[N];
ll f[N];
int n;
ll res=-1e12;
void add(int a,int b){
e[idx]=b;ne[idx]=h[a];h[a]=idx++;
}
ll dfs(int u,int father){
f[u]=w[u];
for(int i=h[u];~i;i=ne[i]){
int j=e[i];
if(j==father) continue;
f[u]+=max(0ll,dfs(j,u));
res=max(res,f[u]);
}
return f[u];
}
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 u,v;cin>>u>>v;
add(u,v);
add(v,u);
}
dfs(1,-1);
cout<<res<<endl;
return 0;
}