fork download 
  1. #include <bits/stdc++.h>
  2. #define FOR(i,a,b) for(int i=(a),_b=(b); i<=_b; ++i)
  3. #define fi first
  4. #define se second
  5. #define el "\n"
  6. #define pb push_back
  7. #define sz(a) (int)(a).size()
  8. #define FILL(a,x) memset(a,x,sizeof(a))
  9. using namespace std;
  10. typedef long long ll;
  11.  
  12. const int MAXN = 100000 + 5;
  13.  
  14. int n, Q;
  15. ll w[MAXN];
  16. vector<int> g[MAXN];
  17. int parentArr[MAXN];
  18. int tin[MAXN], tout[MAXN], subSize[MAXN], timerDFS;
  19.  
  20. ll bit1[MAXN], bit2[MAXN];
  21.  
  22. void bitAdd(ll bit[], int idx, ll val){
  23. while(idx <= n){
  24. bit[idx] += val;
  25. idx += idx & -idx;
  26. }
  27. }
  28.  
  29. ll bitSum(ll bit[], int idx){
  30. ll res = 0;
  31. while(idx > 0){
  32. res += bit[idx];
  33. idx -= idx & -idx;
  34. }
  35. return res;
  36. }
  37.  
  38. void rangeAdd(int l, int r, ll val){
  39. if(l > r) return;
  40. bitAdd(bit1, l, val);
  41. bitAdd(bit1, r + 1, -val);
  42. bitAdd(bit2, l, val * (l - 1));
  43. bitAdd(bit2, r + 1, -val * r);
  44. }
  45.  
  46. ll prefixSum(int idx){
  47. ll s1 = bitSum(bit1, idx);
  48. ll s2 = bitSum(bit2, idx);
  49. return s1 * idx - s2;
  50. }
  51.  
  52. ll rangeSum(int l, int r){
  53. if(l > r) return 0;
  54. return prefixSum(r) - prefixSum(l - 1);
  55. }
  56.  
  57. void dfs(int u, int p){
  58. parentArr[u] = p;
  59. tin[u] = ++timerDFS;
  60. subSize[u] = 1;
  61. for(int i = 0; i < sz(g[u]); ++i){
  62. int v = g[u][i];
  63. if(v == p) continue;
  64. dfs(v, u);
  65. subSize[u] += subSize[v];
  66. }
  67. tout[u] = timerDFS;
  68. }
  69.  
  70. ll totalWeight(){
  71. return rangeSum(1, n);
  72. }
  73.  
  74. ll subtreeSum(int u){
  75. return rangeSum(tin[u], tout[u]);
  76. }
  77.  
  78. int adjustCentroid(int cen){
  79. while(true){
  80. ll tot = totalWeight();
  81. if(tot == 0) return 1;
  82. ll bestW = 0;
  83. int best = -1;
  84.  
  85.     if(parentArr[cen] != 0){
  86.         ll side = tot - subtreeSum(cen);
  87.         if(side > bestW){
  88.             bestW = side;
  89.             best = parentArr[cen];
  90.         }
  91.     }
  92.  
  93.     for(int i = 0; i < sz(g[cen]); ++i){
  94.         int v = g[cen][i];
  95.         if(v == parentArr[cen]) continue;
  96.         ll side = subtreeSum(v);
  97.         if(side > bestW){
  98.             bestW = side;
  99.             best = v;
  100.         }
  101.     }
  102.  
  103.     if(best == -1 || bestW * 2 <= tot) break;
  104.     cen = best;
  105. }
  106. return cen;
  107.  
  108. }
  109.  
  110. int main(){
  111. ios::sync_with_stdio(false);
  112. cin.tie(NULL);
  113. cout.tie(NULL);
  114.  
  115. if(!(cin >> n >> Q)) return 0;
  116. FOR(i,1,n) cin >> w[i];
  117. FOR(i,1,n-1){
  118.     int u, v;
  119.     cin >> u >> v;
  120.     g[u].pb(v);
  121.     g[v].pb(u);
  122. }
  123.  
  124. timerDFS = 0;
  125. dfs(1, 0);
  126.  
  127. FOR(i,1,n){
  128.     rangeAdd(tin[i], tin[i], w[i]);
  129. }
  130.  
  131. int centroid = 1;
  132. centroid = adjustCentroid(centroid);
  133.  
  134. while(Q--){
  135.     int type, u;
  136.     ll c;
  137.     cin >> type >> u >> c;
  138.     if(type == 1){
  139.         rangeAdd(tin[u], tin[u], c);
  140.     } else {
  141.         rangeAdd(tin[u], tout[u], c);
  142.     }
  143.     centroid = adjustCentroid(centroid);
  144.     cout << centroid << el;
  145. }
  146.  
  147. return 0;
  148.  
  149. }
  150.  
Success #stdin #stdout 0.01s 6888KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/dWNC61
language:
C++14 (clang 8.0)
created:
8 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!