```cpp
#include<bits/stdc++.h>
using namespace std;
typedef long long lld;
struct var
{
lld val;
lld chs;//child sum
int cht;//child total
int ch[16005];
var(){}
};var tree[16005];
bool isroot[16005];
lld calc(int bt)
{
for(int i=1;i<=tree[bt].cht;++i)
tree[bt].chs+=calc(tree[bt].ch[i]);
return tree[bt].chs;
}
int dp(int bt)
{
tree[bt].chs=tree[bt].val;
for(int i=1;i<=tree[bt].cht;++i)
if(dp(tree[bt].ch[i])>0)
tree[bt].chs+=tree[tree[bt].ch[i]].chs;
if(tree[bt].chs>0)return tree[bt].chs;
else return 0;
}
void pre(int bt,int tab)
{
if(!bt)return;
for(int i=0;i<tab;++i)
cout<<" ";
printf("%d:%lld\n",bt,tree[bt].chs);
for(int i=1;i<=tree[bt].cht;++i)
{
pre(tree[bt].ch[i],tab+1);
cout<<endl;
}
}
int main()
{
//freopen("input.txt","r",stdin);
//freopen("output.txt","w",stdout);
int n;cin>>n;
for(int i=1;i<=n;++i)
cin>>tree[i].val;
for(int i=1;i<n;++i)
{
int a,b;cin>>a>>b;
tree[b].ch[++tree[b].cht]=a;
isroot[a]=true;
}
int root;
for(root=1;isroot[root];++root);
calc(root);cout<<dp(root)<<endl;
//pre(root,0);
return 0;
}
```
by 瀛洲仙子 @ 2024-03-22 20:47:16