Advertisement
willy108

Quantum Flux

Apr 3rd, 2022
1,109
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 3.86 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. #include <iostream>
  3. #include <vector>
  4. #include <algorithm>
  5. #include <cmath>
  6. #include <string>
  7. #include <string.h>
  8. #include <utility>
  9. #include <map>
  10. #include <list>
  11. using namespace std;
  12. typedef pair <int, int> pii;
  13. typedef long long ll;
  14. #define pb push_back
  15. #define mp make_pair
  16. #define f first
  17. #define s second
  18.  
  19. const int maxn = 5e5 + 10;
  20.  
  21. int n, m;
  22. vector <int> g[maxn];
  23. int par[maxn];
  24.  
  25. void set_parity(int u, int p, int x) {
  26.     par[u] = x;
  27.     for (int v : g[u]) {
  28.         if (v == p) continue;
  29.         set_parity(v, u, x ^ 1);
  30.     }
  31. }
  32.  
  33. int dep[maxn], sz[maxn], son[maxn];
  34.  
  35. void dfs1(int u, int p) {
  36.     dep[u] = dep[p] + 1;
  37.     sz[u] = 1;
  38.     son[u] = -1;
  39.     for (int v : g[u]) {
  40.         if (v == p) continue;
  41.         dfs1(v, u);
  42.         sz[u] += sz[v];
  43.         if (sz[u] == -1 || sz[v] > sz[son[u]]) son[u] = v;
  44.     }
  45. }
  46.  
  47. int seq[maxn], num, id[maxn], top[maxn], fa[maxn];
  48.  
  49. void dfs2(int u, int p) {
  50.     fa[u] = p;
  51.     seq[++num] = u;
  52.     id[u] = num;
  53.     if (son[u] != -1) {
  54.         top[son[u]] = top[u];
  55.         dfs2(son[u], u);
  56.     }
  57.     for (int v : g[u]) {
  58.         if (v == p || v == son[u]) continue;
  59.         top[v] = v;
  60.         dfs2(v, u);
  61.     }
  62. }
  63.  
  64. ll val[maxn * 4][2], add[maxn * 4][2];
  65.  
  66. void pushdown(int t, int l, int r, int tp) {
  67.     int lc = t << 1, rc = t << 1 | 1, mid = (l + r) >> 1;
  68.     add[lc][tp] += add[t][tp];
  69.     val[lc][tp] += add[t][tp] * (mid - l + 1);
  70.     add[rc][tp] += add[t][tp];
  71.     val[rc][tp] += add[t][tp] * (r - mid);
  72.     add[t][tp] = 0;
  73. }
  74.  
  75. void update_helper(int t, int l, int r, int ql, int qr, int v, int tp) {
  76.     if (ql <= l && r <= qr) {
  77.         add[t][tp] += v;
  78.         val[t][tp] += (ll)v * (r - l + 1);
  79.         return;
  80.     }
  81.     if (ql > r || qr < l) return;
  82.     pushdown(t, l, r, tp);
  83.     int lc = t << 1, rc = t << 1 | 1, mid = (l + r) >> 1;
  84.     update_helper(lc, l, mid, ql, qr, v, tp);
  85.     update_helper(rc, mid + 1, r, ql, qr, v, tp);
  86.     val[t][tp] = val[lc][tp] + val[rc][tp];
  87. }
  88.  
  89. void seg_update(int l, int r, int v, int tp) {
  90.     update_helper(1, 1, n, l, r, v, tp);
  91. }
  92.  
  93. void update(int u, int v, int x, int tp) {
  94.     while (top[u] != top[v]) {
  95.         if (dep[top[u]] > dep[top[v]]) swap(u, v);
  96.         seg_update(id[top[v]], id[v], x, tp);
  97.         v = fa[top[v]];
  98.     }
  99.     if (dep[u] > dep[v]) swap(u, v);
  100.     seg_update(id[u], id[v], x, tp);
  101. }
  102.  
  103. ll ans0[2], ans1, cnt0[2], cnt1;
  104.  
  105. ll query_helper(int t, int l, int r, int ql, int qr, int tp) {
  106.     if (ql <= l && r <= qr) return val[t][tp];
  107.     if (l > qr || r < ql) return 0;
  108.     pushdown(t, l, r, tp);
  109.     int lc = t << 1, rc = t << 1 | 1, mid = (l + r) >> 1;
  110.     return query_helper(lc, l, mid, ql, qr, tp) + query_helper(rc, mid + 1, r, ql, qr, tp);
  111. }
  112.  
  113. ll seg_query(int l, int r, int tp) {
  114.     return query_helper(1, 1, n, l, r, tp);
  115. }
  116.  
  117. ll query(int u, int v, int tp) {
  118.     ll ans = 0;
  119.     while (top[u] != top[v]) {
  120.         if (dep[top[u]] > dep[top[v]]) swap(u, v);
  121.         ans += seg_query(id[top[v]], id[v], tp);
  122.         v = fa[top[v]];
  123.     }
  124.     if (dep[u] > dep[v]) swap(u, v);
  125.     ans += seg_query(id[u], id[v], tp);
  126.     return ans;
  127. }
  128.  
  129. int main() {
  130.     scanf("%d%d", &n, &m);
  131.     for (int i = 0; i < n - 1; i++) {
  132.         int u, v;
  133.         scanf("%d%d", &u, &v);
  134.         g[u].pb(v);
  135.         g[v].pb(u);
  136.     }
  137.     set_parity(1, 0, 1);
  138.     dfs1(1, 0);
  139.     dfs2(1, 0);
  140.     for (int i = 0; i < m; i++) {
  141.         int op, u, x;
  142.         scanf("%d%d", &op, &u);
  143.         if (op == 1) {
  144.             scanf("%d", &x);
  145.             ans0[par[u]] += (ll)x * (dep[u] - 1);
  146.             cnt0[par[u]] += x;
  147.             update(1, u, x, par[u]);
  148.         }
  149.         else {
  150.             ll ans;
  151.             ans = ans0[par[u]] - 2 * query(1, u, par[u]) + 2 * query(1, 1, par[u]) + cnt0[par[u]] * (dep[u] - 1);
  152.             printf("%lld\n", ans);
  153.         }
  154.     }
  155. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement