大水题
随便找一个点做根,蓝后累计子树和。
子树和<0的话不取就行了
顺便找个最大值输出
end.
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cctype>
#define re register
using namespace std;
void read(int &x){
char c=getchar();x=; bool f=;
while(!isdigit(c)) f=(f&&c!='-'),c=getchar();
while(isdigit(c)) x=(x<<)+(x<<)+(c^),c=getchar();
x=f?x:-x;
}
int max(int &a,int &b){return a>b?a:b;}
#define N 16002
int n,f[N],val[N],ans=-;
int cnt,hd[N],nxt[N<<],ed[N],poi[N<<];
void adde(int x,int y){
nxt[ed[x]]=++cnt; hd[x]=hd[x]?hd[x]:cnt;
ed[x]=cnt; poi[cnt]=y;
}
void dfs(int x,int fa){
f[x]=val[x];
for(int i=hd[x];i;i=nxt[i]){
int to=poi[i];
if(to==fa) continue;
dfs(to,x);
if(f[to]>) f[x]+=f[to];//子树和>0才取
}ans=max(ans,f[x]);
}
int main(){
read(n); int q1,q2;
for(re int i=;i<=n;++i) read(val[i]);
for(re int i=;i<n;++i){
read(q1); read(q2);
adde(q1,q2); adde(q2,q1);
}dfs(,);
printf("%d",ans);
return ;
}