fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. using ll = long long;
  4.  
  5. int main(){
  6.     ios::sync_with_stdio(false);
  7.     cin.tie(nullptr);
  8.  
  9.     int t;
  10.     cin >> t;
  11.     while (t--){
  12.         int n;
  13.         cin >> n;
  14.  
  15.         vector<ll>a(n+1);
  16.         for(int i = 1; i <= n; i++)
  17.             cin >> a[i];
  18.  
  19.         // build adjacency
  20.         vector<vector<int>> adj(n+1);
  21.         for(int i = 0; i < n-1; i++){
  22.             int u, v;
  23.             cin >> u >> v;
  24.             adj[u].push_back(v);
  25.             adj[v].push_back(u);
  26.         }
  27.  
  28.         vector<ll> f(n+1), h(n+1);
  29.         vector<int> parent(n+1, 0);
  30.         queue<int> q;
  31.  
  32.         // initialize root = 1
  33.         parent[1] = -1;
  34.         f[1] = a[1];
  35.         h[1] = -a[1];
  36.         q.push(1);
  37.  
  38.         // BFS from root
  39.         while(!q.empty()){
  40.             int i = q.front(); 
  41.             q.pop();
  42.             for(int j : adj[i]){
  43.                 if (parent[j] == 0){
  44.                     parent[j] = i;
  45.                     // compute DP for child j
  46.                     f[j] = max(a[j], a[j] + h[i]);
  47.                     h[j] = max(-a[j], -a[j] + f[i]);
  48.                     q.push(j);
  49.                 }
  50.             }
  51.         }
  52.  
  53.         // output threats = f[i]
  54.         for(int i = 1; i <= n; i++){
  55.             cout << f[i] << (i==n?'\n':' ');
  56.         }
  57.     }
  58.  
  59.     return 0;
  60. }
  61.  
Success #stdin #stdout 0s 5308KB
comments (?)
stdin
copy 
2
5
4 5 2 6 7
1 2
3 2
4 3
5 1
6
1000000000 500500500 900900900 9 404 800800800
3 4
5 1
2 5
1 6
6 4
stdout
copy 
4 5 2 9 7
1000000000 1500500096 1701701691 199199209 404 800800800
https://ideone.com/vFC8KK
language:
C++ (gcc 8.3)
created:
5 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!