fork download 
  1. #include <iostream>
  2. #include <vector>
  3. #include <queue>
  4.  
  5. using namespace std;
  6.  
  7. int main() {
  8.     // Fast I/O
  9.     ios_base::sync_with_stdio(false);
  10.     cin.tie(NULL);
  11.  
  12.     int n;
  13.     if (!(cin >> n)) return 0;
  14.  
  15.     vector<int> val(n + 1);
  16.     vector<vector<int>> adj(n + 1);
  17.     vector<int> ans(n + 1, 0);
  18.     vector<bool> visited(n + 1, false);
  19.  
  20.     // Read the values (0 or 1) for each node
  21.     for (int i = 1; i <= n; ++i) {
  22.         cin >> val[i];
  23.     }
  24.  
  25.     // Read the N-1 edges and build the adjacency list
  26.     for (int i = 0; i < n - 1; ++i) {
  27.         int u, v;
  28.         cin >> u >> v;
  29.         adj[u].push_back(v);
  30.         adj[v].push_back(u);
  31.     }
  32.  
  33.     // Initialize BFS Queue with the root node
  34.     queue<int> q;
  35.     q.push(1);
  36.     visited[1] = true;
  37.  
  38.     // The root's path sum is just its own value
  39.     ans[1] = val[1];
  40.  
  41.     // Standard BFS traversal
  42.     while (!q.empty()) {
  43.         int current = q.front();
  44.         q.pop();
  45.  
  46.         // Check all connected neighbors
  47.         for (int neighbor : adj[current]) {
  48.             if (!visited[neighbor]) {
  49.                 visited[neighbor] = true;
  50.  
  51.                 // Child's accumulated total = Parent's accumulated total + Child's value
  52.                 ans[neighbor] = ans[current] + val[neighbor];
  53.  
  54.                 q.push(neighbor);
  55.             }
  56.         }
  57.     }
  58.  
  59.     // Print the result for each node
  60.     for (int i = 1; i <= n; ++i) {
  61.         if (i == 1) {
  62.             cout << ans[i];
  63.         } else {
  64.             cout << " " << ans[i];
  65.         }
  66.     }
  67.     cout << "\n";
  68.  
  69.     return 0;
  70. }
Success #stdin #stdout 0s 5320KB
comments (?)
stdin 
5
1 0 1 1 0
1 2
1 3
2 4
2 5
stdout 
1 1 2 2 1
https://ideone.com/6AhLj1
tree 1
language:
C++ (gcc 8.3)
created:
13 days 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!