fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. const long long MaxN = 1e5 + 5;
  4. long long n, a[MaxN],dp[MaxN];
  5. vector<long long> vt[MaxN];
  6. void dfs(long long u, long long par)
  7. {
  8.     for (long long v : vt[u])
  9.     {
  10.         if(v==par) continue;
  11.         dfs(v,u);
  12.         dp[u]+=max(dp[v],0LL);
  13.     }
  14. }
  15. void input()
  16. {
  17.     cin >> n;
  18.     for (long long i=1; i<=n; i++)
  19.     {
  20.         cin >> a[i];
  21.     }
  22.     for (long long i=1; i<n ;i++)
  23.     {
  24.         long long u,v;
  25.         cin >> u >> v;
  26.         vt[u].push_back(v);
  27.         vt[v].push_back(u);
  28.     }
  29. }
  30. void solve()
  31. {
  32.     for (long long i=1; i<=n; i++)
  33.     {
  34.         dp[i]=a[i];
  35.     }
  36.     dfs(1,-1);
  37.     long long ans=LLONG_MIN;
  38.     for (long long i=1; i<=n; i++)
  39.     {
  40.         ans=max(ans,dp[i]);
  41.     }
  42.     cout << ans << "\n";
  43. }
  44. int main()
  45. {
  46.     ios_base::sync_with_stdio(0);
  47.     cin.tie(0);
  48.     input();
  49.     solve();
  50. }
  51.  
Success #stdin #stdout 0.01s 6328KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
-9223372036854775808
https://ideone.com/u6xA0B
language:
C++14 (gcc 8.3)
created:
9 hours ago
visibility:
public

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!