fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define Task "last"
  5. #define int long long
  6. #define el '\n'
  7. #define cnt_bit_1 __builtin_popcountll
  8. #define float double
  9. #define IO freopen(Task".inp","r",stdin); freopen(Task".out","w",stdout);
  10. #define pii pair<int,int>
  11. #define fi first
  12. #define se second
  13. #define pb push_back
  14.  
  15. const int N = 1000005;
  16. const int INF = 1e18;
  17. const int MOD = 1e9+7;
  18.  
  19. int n , q , ti = 0;
  20. vector<pii> ke[N];
  21. int A[N] , sz[N], par[N], dep[N], heavy[N], head[N], pos[N];
  22. int distr[N] , wei[N], pre[N] , bA[N] , bitt[N];
  23.  
  24. void dfs(int u , int p , int d , int dist , int up)
  25. {
  26.     sz[u] = 1; par[u] = p; dep[u] = d; distr[u] = dist; wei[u] = up; heavy[u] = 0;
  27.     int ms = 0;
  28.     for(auto &edge : ke[u])
  29.     {
  30.         int v = edge.fi, w = edge.se;
  31.         if(v != p)
  32.         {
  33.             dfs(v, u, d + 1, dist + w, w);
  34.             sz[u] += sz[v];
  35.             if(sz[v] > ms)
  36.             {
  37.                 ms = sz[v];
  38.                 heavy[u] = v;
  39.             }
  40.         }
  41.     }
  42. }
  43.  
  44. void HLD(int u , int p , int h)
  45. {
  46.     head[u] = h;
  47.     pos[u] = ++ti;
  48.     pre[ti] = pre[ti - 1] + wei[u];
  49.  
  50.     if(heavy[u]) HLD(heavy[u], u, h);
  51.     for(auto &edge : ke[u])
  52.     {
  53.         int v = edge.fi;
  54.         if(v != p && v != heavy[u])
  55.         {
  56.             HLD(v, u, v);
  57.         }
  58.     }
  59. }
  60.  
  61. void add(int idx, int val1, int val2)
  62. {
  63.     for(; idx <= n; idx += idx & -idx)
  64.     {
  65.         bA[idx] += val1;
  66.         bitt[idx] += val2;
  67.     }
  68. }
  69.  
  70. void range(int L , int R , int d)
  71. {
  72.     add(L , d , d * pre[L - 1]);
  73.     add(R + 1 , -d , -d * pre[R]);
  74. }
  75.  
  76. int query1(int idx)
  77. {
  78.     int sum1 = 0, sum2 = 0;
  79.     int orz = idx;
  80.     for(; idx > 0; idx -= idx & -idx)
  81.     {
  82.         sum1 += bA[idx];
  83.         sum2 += bitt[idx];
  84.     }
  85.     return pre[orz] * sum1 - sum2;
  86. }
  87.  
  88. int range2(int L, int R)
  89. {
  90.     return query1(R) - query1(L - 1);
  91. }
  92.  
  93. void update(int u, int d)
  94. {
  95.     while(u > 0)
  96.     {
  97.         int h = head[u];
  98.         range(pos[h], pos[u], d);
  99.         u = par[h];
  100.     }
  101. }
  102.  
  103. int query2(int u)
  104. {
  105.     int ans = 0;
  106.     while(u > 0)
  107.     {
  108.         int h = head [u];
  109.         ans += range2(pos[h] , pos[u]);
  110.         u = par[h];
  111.     }
  112.     return ans;
  113. }
  114.  
  115. signed main()
  116. {
  117.     ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  118.     IO
  119.  
  120.     cin >> n >> q;
  121.  
  122.     for(int i = 1 ; i < n ; i++)
  123.     {
  124.         int u , v , w; cin >> u >> v >> w;
  125.         ke[u].pb({v, w});
  126.         ke[v].pb({u, w});
  127.     }
  128.  
  129.     dfs(1 , 0 , 1 , 0 , 0);
  130.     HLD(1 , 0 , 1);
  131.  
  132.     int sumA = 0 , sumAD = 0;
  133.  
  134.     q++; /// a bị lừa rồi các e ơi =))
  135.     while(q--)
  136.     {
  137.         int type; cin >> type;
  138.         if(type == 1)
  139.         {
  140.             int x , y; cin >> x >> y;
  141.             int d = y - A[x];
  142.             A[x] = y;
  143.             sumA += d;
  144.             sumAD += d * distr[x];
  145.             update(x , d);
  146.         }
  147.         else
  148.         {
  149.             int x; cin >> x;
  150.             int ans = sumA * distr[x] + sumAD - 2 * query2(x);
  151.             cout << ans << el;
  152.         }
  153.     }
  154.  
  155.     return 0;
  156. }
  157.  
  158. /// q(log * log N) - hld and fenwick sol - VOI
  159.  
Success #stdin #stdout 0.01s 44768KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/yWr8fl
language:
C++14 (clang 8.0)
created:
2 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!