fork download
copy 
  1.  
  2. #include <iostream>
  3. #include <vector>
  4. #include <algorithm>
  5. #include <queue>
  6. #include <map>
  7. #include <set>
  8. #include <bits/stdc++.h>
  9. using namespace std;
  10. #include <ext/pb_ds/assoc_container.hpp>
  11. using namespace __gnu_pbds;
  12. template <class T>
  13. using orderStaticTree =
  14.     tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
  15.  
  16. #define ll long long
  17.  
  18. #define saleh                         \
  19.     ios_base::sync_with_stdio(false); \
  20.     cin.tie(nullptr);
  21.  
  22. const int md = 1e9 + 7;
  23. #define ll long long
  24.  
  25. const ll remo = -1e18;
  26.  
  27. struct Node
  28. {
  29.     ll maxi, ind;
  30. };
  31.  
  32. struct SegmentTree
  33. {
  34.     ll n;
  35.     vector<Node> segData;
  36.     vector<ll> lazy;
  37.  
  38.     SegmentTree(const vector<ll> &v)
  39.     {
  40.         n = v.size();
  41.         segData.resize(4 * n);
  42.         lazy.assign(4 * n, 0);
  43.         build(1, 0, n - 1, v);
  44.     }
  45.  
  46.     void build(ll x, ll l, ll r, const vector<ll> &v)
  47.     {
  48.         if (l == r)
  49.         {
  50.             segData[x] = {v[l], l};
  51.         }
  52.         else
  53.         {
  54.             ll m = (l + r) / 2;
  55.             build(2 * x, l, m, v);
  56.             build(2 * x + 1, m + 1, r, v);
  57.             segData[x] = merge(segData[2 * x], segData[2 * x + 1]);
  58.         }
  59.     }
  60.  
  61.     void push(ll x, ll l, ll r)
  62.     {
  63.         if (lazy[x] != 0)
  64.         {
  65.             segData[x].maxi += lazy[x];
  66.             if (l != r)
  67.             {
  68.                 lazy[2 * x] += lazy[x];
  69.                 lazy[2 * x + 1] += lazy[x];
  70.             }
  71.             lazy[x] = 0;
  72.         }
  73.     }
  74.  
  75.     Node merge(Node a, Node b)
  76.     {
  77.         if (a.maxi > b.maxi)
  78.             return a;
  79.         if (b.maxi > a.maxi)
  80.             return b;
  81.         return (a.ind < b.ind ? b : a);
  82.     }
  83.  
  84.     void addd(ll x, ll l, ll r, ll ql, ll qr, ll val)
  85.     {
  86.         push(x, l, r);
  87.         if (r < ql || l > qr)
  88.             return;
  89.         if (ql <= l && r <= qr)
  90.         {
  91.             lazy[x] += val;
  92.             push(x, l, r);
  93.             return;
  94.         }
  95.         ll m = (l + r) / 2;
  96.         addd(2 * x, l, m, ql, qr, val);
  97.         addd(2 * x + 1, m + 1, r, ql, qr, val);
  98.         segData[x] = merge(segData[2 * x], segData[2 * x + 1]);
  99.     }
  100.  
  101.     Node maxx(ll x, ll l, ll r, ll ql, ll qr)
  102.     {
  103.         push(x, l, r);
  104.         if (r < ql || l > qr)
  105.             return {remo, -1};
  106.         if (ql <= l && r <= qr)
  107.             return segData[x];
  108.         ll m = (l + r) / 2;
  109.         Node left = maxx(2 * x, l, m, ql, qr);
  110.         Node right = maxx(2 * x + 1, m + 1, r, ql, qr);
  111.         return merge(left, right);
  112.     }
  113.  
  114.     void remove(ll x, ll l, ll r, ll idx)
  115.     {
  116.         push(x, l, r);
  117.         if (l == r)
  118.         {
  119.             segData[x] = {remo, l};
  120.             return;
  121.         }
  122.         ll m = (l + r) / 2;
  123.         if (idx <= m)
  124.             remove(2 * x, l, m, idx);
  125.         else
  126.             remove(2 * x + 1, m + 1, r, idx);
  127.         segData[x] = merge(segData[2 * x], segData[2 * x + 1]);
  128.     }
  129.  
  130.     Node get_max()
  131.     {
  132.         return maxx(1, 0, n - 1, 0, n - 1);
  133.     }
  134.  
  135.     void update_suffix(ll from)
  136.     {
  137.         if (from < n - 1)
  138.             addd(1, 0, n - 1, from + 1, n - 1, -1);
  139.     }
  140.  
  141.     void erase(ll idx)
  142.     {
  143.         remove(1, 0, n - 1, idx);
  144.     }
  145. };
  146.  
  147. const int maxi = 2e5 + 5;
  148. vector<int> tre[maxi];
  149. vector<int> used;
  150. int par[maxi];
  151. ll a[maxi];
  152. ll ansi[maxi];
  153.  
  154. void preCal(int node, int parnt)
  155. {
  156.     par[node] = parnt;
  157.     for (int child : tre[node])
  158.     {
  159.         if (child != parnt)
  160.         {
  161.             preCal(child, node);
  162.         }
  163.     }
  164. }
  165.  
  166. int main()
  167. {
  168.     saleh;
  169.     int t;
  170.     scanf("%d", &t);
  171.     while (t--)
  172.     {
  173.         int n;
  174.         scanf("%d", &n);
  175.  
  176.         for (int i = 1; i <= n; ++i)
  177.             scanf("%lld", &a[i]);
  178.  
  179.         used.clear();
  180.  
  181.         for (int i = 0; i < n - 1; ++i)
  182.         {
  183.             int u, v;
  184.             scanf("%d %d", &u, &v);
  185.             tre[u].push_back(v);
  186.             tre[v].push_back(u);
  187.             used.push_back(u);
  188.             used.push_back(v);
  189.         }
  190.  
  191.         preCal(1, 0);
  192.  
  193.         for (int i = 1; i <= n; ++i)
  194.         {
  195.             ll sum = 0;
  196.             ll maxi = a[i];
  197.             ll altr = 1;
  198.             int node = i;
  199.  
  200.             sum = 0;
  201.             altr = 1;
  202.             while (node != 0)
  203.             {
  204.                 sum += altr * a[node];
  205.                 maxi = max(maxi, sum);
  206.                 node = par[node];
  207.                 altr *= -1;
  208.             }
  209.  
  210.             ansi[i] = maxi;
  211.         }
  212.  
  213.         for (int i = 1; i <= n; ++i)
  214.             printf("%lld ", ansi[i]);
  215.         printf("\n");
  216.         for (int i : used)
  217.             tre[i].clear();
  218.     }
  219.  
  220.     return 0;
  221. }
Success #stdin #stdout 0.01s 9800KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy
https://ideone.com/QAuLOw
language:
C++ (gcc 8.3)
created:
15 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!