fork download
copy 
  1. // nxhhoang - the dreamer
  2. // g++ -std=c++11 -Wall -Wextra -O2 B.cpp -o B.exe
  3.  
  4. // __builtin_popcount(x); - count bits 1
  5. // __builtin_parity(x); nums of 1 (even or odd)
  6. // __builtin_ctz(x); count trailing zeros
  7. // __builtin_clz(x); count leading zeros
  8.  
  9. #include <bits/stdc++.h>
  10.  
  11. #define FOR(i, a, b) for (int i = (a), _b = (b); i < _b; i++)
  12. #define endl '\n'
  13. #define debug(x) cout << #x << " = " << x << '\n'
  14. #define ub upper_bound // find target < min(value)
  15. #define lb lower_bound // find target <= min(value)
  16. #define fi first
  17. #define se second
  18. #define SIZE(x) (int)(x).size()
  19.  
  20. #define all(a) (a).begin(), (a).end()
  21. #define pii pair<int, int>
  22. #define pll pair<ll, ll>
  23. #define vi vector<int>
  24. #define vll vector<ll>
  25. using namespace std;
  26. using ll = long long;
  27. using ull = unsigned long long;
  28.  
  29. const int MSIZE = 2e5 + 5;
  30. const int MAXN = 4e7 + 5;
  31. const int MOD = 1e9 + 7;
  32. const int dx[] = {1, -1, 0, 0};
  33. const int dy[] = {0, 0, 1, -1};
  34.  
  35. const int LOG = 19;
  36.  
  37. vector<vi> tre(MSIZE);
  38. int euler[2 * MSIZE], in[MSIZE], out[MSIZE], height[MSIZE];
  39. int timer = 1;
  40. vector<vi> rmq(MSIZE, vi(20, 0));
  41.  
  42. struct SegmentTree {
  43.     vector<ll> val;
  44.     vector<int> cong;
  45.     vector<ll> lazy;
  46.  
  47.     void build(int idx, int l, int r) {
  48.         if (l == r) {
  49.             if (euler[l] == -1) cong[idx]--;
  50.             else cong[idx]++;
  51.             return;
  52.         }
  53.  
  54.         int mid = (l + r) >> 1;
  55.         build(2 * idx, l, mid);
  56.         build(2 * idx + 1, mid + 1, r);
  57.         cong[idx] = cong[idx * 2] + cong[idx * 2 + 1];
  58.     }
  59.  
  60.     SegmentTree(int n) {
  61.         val.assign(4 * n + 1, 0);
  62.         cong.assign(4 * n + 1, 0);
  63.         lazy.assign(4 * n + 1, 0);
  64.         build(1, 1, n);
  65.     }
  66.  
  67.     void pushLazy(int idx, int l, int r) {
  68.         if (lazy[idx] == 0) return;
  69.         val[idx] += cong[idx] * lazy[idx];
  70.         if (l < r) {
  71.             lazy[2 * idx] += lazy[idx];
  72.             lazy[2 * idx + 1] += lazy[idx];
  73.         }
  74.         lazy[idx] = 0;
  75.     }
  76.  
  77.     void update(int idx, int l, int r, int x, int y, ll tri) {
  78.         pushLazy(idx, l, r);
  79.         if (y < l || r < x) return;
  80.  
  81.         if (x <= l && r <= y) {
  82.             lazy[idx] += tri;
  83.             pushLazy(idx, l, r);
  84.             return;
  85.         }
  86.  
  87.         int mid = (l + r) >> 1;
  88.         update(idx * 2, l, mid, x, y, tri);
  89.         update(idx * 2 + 1, mid + 1, r, x, y, tri);
  90.  
  91.         val[idx] = val[2 * idx] + val[2 * idx + 1];
  92.     }
  93.  
  94.     void point_update(int idx, int l, int r, int pos, ll tri) {
  95.         if (l == r) {
  96.             lazy[idx] += tri;
  97.             pushLazy(idx, l, r);
  98.             return;
  99.         }
  100.  
  101.         int mid = (l + r) >> 1;
  102.         if (pos <= mid) point_update(2 * idx, l, mid, pos, tri);
  103.         else point_update(2 * idx + 1, mid + 1, r, pos, tri);
  104.         val[idx] = val[2 * idx] + val[2 * idx + 1];
  105.     }
  106.  
  107.     ll query(int idx, int l, int r, int x, int y) {
  108.         pushLazy(idx, l, r);
  109.         if (y < l || r < x) return 0;
  110.  
  111.         if (x <= l && r <= y) {
  112.             return val[idx];
  113.         }
  114.  
  115.         int mid = (l + r) >> 1;
  116.         return query(idx * 2, l, mid, x, y) + query(idx * 2 + 1, mid + 1, r, x, y);
  117.     }
  118.  
  119.     ll point_query(int idx, int l, int r, int pos) {
  120.         pushLazy(idx, l, r);
  121.         if (l == r) return val[idx];
  122.  
  123.         int mid = (l + r) >> 1;
  124.         if (pos <= mid) return point_query(idx * 2, l, mid, pos);
  125.         else return point_query(idx * 2 + 1, mid + 1, r, pos);
  126.     }
  127. };
  128.  
  129. void dfs(int u, int p) {
  130.     rmq[u][0] = p;
  131.     height[u]++;
  132.     euler[timer++] = u;
  133.  
  134.     for (int i = 1; i < LOG; i++) {
  135.         rmq[u][i] = rmq[rmq[u][i - 1]][i - 1];
  136.     }
  137.  
  138.     for (int ve : tre[u]) {
  139.         if (ve == p) continue;
  140.         height[ve] = height[u];
  141.         dfs(ve, u);
  142.     }
  143.     euler[timer++] = u;
  144. }
  145.  
  146. int LCA(int u, int v) {
  147.     if (height[u] < height[v]) swap(u, v);
  148.  
  149.     int len = height[u] - height[v];
  150.     for (int i = LOG - 1; i >= 0; i--) {
  151.         if (len & (1 << i)) u = rmq[u][i];
  152.     }
  153.  
  154.     if (u == v) return u;
  155.  
  156.     for (int i = LOG - 1; i >= 0; i--) {
  157.         if (rmq[u][i] != rmq[v][i]) {
  158.             u = rmq[u][i];
  159.             v = rmq[v][i];
  160.         }
  161.     }
  162.     return rmq[u][0];
  163. }
  164.  
  165. void solve()
  166. {
  167.     int n, q;
  168.     cin >> n >> q;
  169.  
  170.     for (int i = 0; i < n - 1; i++) {
  171.         int a, b;
  172.         cin >> a >> b;
  173.  
  174.         tre[a].push_back(b);
  175.         tre[b].push_back(a);
  176.     }
  177.  
  178.     dfs(1, 1);
  179.  
  180.     for (int i = 1; i < timer; i++) {
  181.         if (in[euler[i]] == 0) in[euler[i]] = i;
  182.         out[euler[i]] = i;
  183.     }
  184.  
  185.     for (int i = 1; i <= n; i++) euler[in[i]] = 1, euler[out[i]] = -1;
  186.     int m = timer - 1;
  187.     SegmentTree tree(m);
  188.  
  189.     while (q--) {
  190.         int t, u, x;
  191.         cin >> t >> u >> x;
  192.  
  193.  
  194.         if (t == 1) {
  195.             tree.update(1, 1, m, in[u], out[u], x);
  196.         } else if (t == 2) {
  197.             tree.point_update(1, 1, m, in[u], x);
  198.             tree.point_update(1, 1, m, out[u], x);
  199.         } else {
  200.             int v = x;
  201.             int uv = LCA(u, v);
  202.             ll d1u = tree.query(1, 1, m, in[uv], in[u]);
  203.             ll d1v = tree.query(1, 1, m, in[uv], in[v]);
  204.             ll val_uv = tree.query(1, 1, m, in[uv], in[uv]);
  205.  
  206.             ll res = d1u + d1v - val_uv;
  207.             cout << res << endl;
  208.         }
  209.     }
  210. }
  211.  
  212. int main()
  213. {
  214.     ios_base::sync_with_stdio(false);
  215.     cin.tie(NULL);
  216.     // freopen("K-query.inp", "r", stdin);
  217.     // freopen("K-query.ans", "w", stdout)
  218.     int t = 1;
  219.     // cin >> t; // DLLLLLLLLLLLLLLLLLLLLLLLLLLLLLL
  220.  
  221.  
  222.     while (t--)
  223.     {
  224.         solve();
  225.     }
  226.     return 0;
  227. }
Success #stdin #stdout 0.04s 31448KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/RzGPQT
language:
C++14 (gcc 8.3)
created:
14 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!