1 #include<cstdio> 2 #include<vector> 3 #include<algorithm> 4 const int N=6001; 5 std::vector<int> c[N]; 6 int r[N],p[N]={0}; 7 inline void add_edge(const int a,const int b) { 8     c[a].push_back(b); 9     p[b]=a;10 }11 std::pair<int,int> dfs(const int p) {12     int w1=r[p],w2=0;13     for(unsigned int i=0;i<c[p].size();i++) {14         std::pair<int,int> t=dfs(c[p][i]);15         if(t.second>0) w1+=t.second;16         if(t.first>0) w2+=t.second?std::max(t.first,t.second):t.first;17     }18     return std::make_pair(w1,w2);19 }20 int main() {21     int n;22     scanf("%d",&n);23     for(int i=1;i<=n;i++) scanf("%d",&r[i]);24     for(int i=1;i<n;i++) {25         int l,k;26         scanf("%d%d",&l,&k);27         add_edge(k,l);28     }29     int root;30     for(int i=1;i<=n;i++) {31         if(!p[i]) {32             root=i;33             break;34         }35     }36     std::pair<int,int> ans=dfs(root);37     printf("%d\n",std::max(ans.first,ans.second));38     return 0;39 }