#include <cstdio> #include <vector> #include <cstring> #include <iostream> #include <algorithm> using namespace std; const int maxn = 6100; vector<int> G[maxn]; int d[maxn][2],c[maxn]; /* 1 该节点已经选取 0 该节点未选区 */ bool vis[maxn][2]; int dp(int i,int j,int f){ if(vis[i][j]) return d[i][j]; vis[i][j] =true; if(G[i].size()==1&&G[i][0]==f){ return d[i][j] = 0; } d[i][j]=0; for(int k=0;k<G[i].size();k++){ if(G[i][k]==f) continue; if(j&1) d[i][j]+=dp(G[i][k],0,i); else d[i][j]+=max(dp(G[i][k],0,i),dp(G[i][k],1,i)+c[G[i][k]]); } return d[i][j]; } int main() { int n; while(scanf("%d",&n)==1){ for(int i=1;i<=n;i++){ G[i].clear(); scanf("%d",&c[i]); } for(int i=1;i<=n;i++){ int x,y; scanf("%d %d",&x,&y); if(!x||!y) break; G[x].push_back(y); G[y].push_back(x); } memset(vis,false,sizeof(vis)); printf("%d\n",max(dp(1,0,-1),dp(1,1,-1)+c[1])); } return 0; }