fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. long long sum[500000 + 5];
  5. long long b[500000 + 5];
  6.  
  7. long long DFS(long long node, vector<long long> G[], long long used[], long long parent[]) {
  8.     used[node] = 1;
  9.     sum[node] = b[node];
  10.  
  11.     for (long long neighbour : G[node]) {
  12.         if (used[neighbour] == 0) {
  13.             parent[neighbour] = node;
  14.             sum[node] += DFS(neighbour, G, used, parent);
  15.         }
  16.     }
  17.  
  18.     return sum[node];
  19. }
  20.  
  21. int main() {
  22.     long long n;
  23.     cin >> n;
  24.  
  25.     vector<long long> G[n + 1];
  26.  
  27.     for (long long i = 1; i <= n; i++) {
  28.         cin >> b[i];
  29.     }
  30.  
  31.     for (long long i = 1; i <= n - 1; i++) {
  32.         long long u, v;
  33.         cin >> u >> v;
  34.  
  35.         G[u].push_back(v);
  36.         G[v].push_back(u);
  37.     }
  38.  
  39.     long long used[n + 1] = {};
  40.     long long parent[n + 1] = {};
  41.  
  42.     DFS(1, G, used, parent);
  43.  
  44.     long long answer = -1000000000000000LL;
  45.  
  46.     for (long long i = 1; i <= n; i++) {
  47.         answer = max(answer, sum[i]);
  48.     }
  49.  
  50.     cout << answer;
  51.  
  52.     return 0;
  53. }
Success #stdin #stdout 0s 5688KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/PuSiQ2
language:
C++14 (gcc 8.3)
created:
1 day 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!