应该是0啊,一个也不选
by SofanHe @ 2017-10-17 20:30:11
这是我的做法,应该可以解决你的问题
```cpp
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int maxn=2e4;
int a[maxn],dp[maxn][2],g[maxn];
int n,tot;
struct line
{
int next,to;
}edge[maxn*2];
void add1(int a,int b)
{
edge[++tot].next=g[a];
edge[tot].to=b;
g[a]=tot;
}
void dfs(int cur,int fa)
{
dp[cur][1]=a[cur];
for(int i=g[cur];i;i=edge[i].next)
{
if(edge[i].to==fa)continue;
dfs(edge[i].to,cur);
dp[cur][1]=max(dp[cur][1],dp[cur][1]+dp[edge[i].to][1]);
dp[cur][0]=max(dp[cur][0],dp[edge[i].to][1]);
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin>>n;
memset(dp,-0x3f,sizeof(dp));
for(int i=1;i<=n;i++)cin>>a[i];
for(int i=1;i<n;i++)
{
int x=0,y=0;
cin>>x>>y;
add1(x,y);
add1(y,x);
}
dfs(1,0);
cout<<max(dp[1][1],dp[1][0]);
return 0;
}
```
by ysj1173886760 @ 2018-08-17 13:46:18
@[安国华](/space/show?uid=26652) 是啊,我也想到这一点了
by 青珹 @ 2018-11-03 07:06:57
不过应该是输出最大的负数(绝对值最小)
by 青珹 @ 2018-11-03 07:07:47