fork(1) download
copy 
  1. # include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. long long ans,dp[100005],score[100005];
  5. vector<int> edge[100005];
  6.  
  7. void DFS(int n,int parent)
  8. {
  9.     dp[n]=score[n];
  10.     for(int i=0;i<edge[n].size();i++)
  11.     {
  12.         if(edge[n][i]!=parent)
  13.         {
  14.             DFS(edge[n][i],n);
  15.                 if(dp[edge[n][i]]>0)
  16.                     dp[n]+=dp[edge[n][i]];
  17.         }
  18.     }
  19.     ans=max(ans,dp[n]);
  20. }
  21.  
  22. int main()
  23. {
  24.     int t;
  25.     cin>>t;
  26.     while(t--)
  27.     {
  28.         int N;
  29.         scanf("%d",&N);
  30.         for(int i=1;i<=N;i++)
  31.             scanf("%lld",&score[i]);
  32.  
  33.         for(int i=1;i<=N;i++)
  34.             edge[i].clear();
  35.         int u,v;
  36.         for(int i=0;i<N-1;i++)
  37.         {
  38.             scanf("%d%d",&u,&v);
  39.             edge[u].push_back(v);
  40.             edge[v].push_back(u);
  41.         }
  42.         ans=score[1];
  43.         DFS(1,-1);
  44.         cout<<ans<<endl;
  45.     }
  46.     return 0;
  47. }
  48.  
Success #stdin #stdout 0s 6208KB
comments (?)
stdin
copy 
1
5
5 -1 2 3 -4
1 2
3 1
4 5
1 4
stdout
copy 
10
https://ideone.com/y58vEm
language:
C++14 (gcc 8.3)
created:
7 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!