传送门
思路:
任意找一个点为树根。DFS 遍历树,如果子树和为负就直接跳过,不然就统计进答案。( 虽是任意取一点为根,但不一定从这个点出发能够取得最优解,要开一个 ans 记录一下最大值。)
标程:
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<string>
#include<cstdlib>
#include<stack>
#include<vector>
#include<queue>
#include<deque>
#include<map>
#include<set>
using namespace std;
#define lck_max(a,b) ((a)>(b)?(a):(b))
#define lck_min(a,b) ((a)<(b)?(a):(b))
#define maxn 16002
typedef long long LL;
LL sum[maxn],n;
LL head[maxn<<],cnt=;
vector<LL>son[maxn];
LL w[maxn],ans=-maxn;
struct hh
{
LL nex,to;
}t[maxn<<];
inline LL read()
{
LL kr=,xs=;
char ls;
ls=getchar();
while(!isdigit(ls))
{
if(!(ls^))
kr=-;
ls=getchar();
}
while(isdigit(ls))
{
xs=(xs<<)+(xs<<)+(ls^);
ls=getchar();
}
return xs*kr;
}
LL u,v;
inline void add(LL nex,LL to)
{
t[++cnt].nex=head[nex];
t[cnt].to=to;
head[nex]=cnt;
}
inline void dfs(LL u,LL fa)
{
for(LL i=head[u];i;i=t[i].nex)
{
LL v=t[i].to;
if(v==fa) continue;
son[u].push_back(v);
dfs(v,u);
}
if(son[u].size())
{
for(LL j=;j<son[u].size();j++)
{
if(w[son[u][j]]<) continue;
w[u]+=w[son[u][j]];
}
}
w[u]+=sum[u];
ans=lck_max(ans,w[u]);
return ;
}
int main()
{
//freopen("t.in","r",stdin);
n=read();
for(LL i=;i<=n;i++)
sum[i]=read();
for(LL i=;i<n;i++)
{
u=read();v=read();add(u,v);add(v,u);
}
dfs(,);
printf("%lld\n",ans);
return ;
}