不用找根节点,任选一个点为根节点就行,但是边要加双向边
#include<bits/stdc++.h>
using namespace std;
const int N=50000;
int f[N][2];
int happy[N];
int n;
int din[N];
int ne[N],ver[N],head[N],idx;
void add(int x,int y)
{
ne[idx]=head[x];
ver[idx]=y;
head[x]=idx;
idx++;
}
void dp(int x,int father)
{
f[x][1]=happy[x];
for(int i=head[x];i!=-1;i=ne[i])
{
int y=ver[i];
if(y==father)continue;
dp(y,x);
f[x][0]+=max(f[y][1],f[y][0]);
f[x][1]+=f[y][0];
}
}
int main()
{
memset(head,-1,sizeof(head));
cin>>n;
for(int i=1;i<=n;i++)
cin>>happy[i];
for(int i=1;i<n;i++)
{
int a,b;
cin>>a>>b;
add(b,a);
add(a,b);
}
dp(1,0);
cout<<max(f[1][0],f[1][1]);
return 0;
}