fork download
copy 
  1. // ~~ icebear ~~
  2. #include <bits/stdc++.h>
  3. using namespace std;
  4.  
  5. typedef long long ll;
  6. typedef pair<int, int> ii;
  7. typedef pair<int, ii> iii;
  8.  
  9. template<class T>
  10.     bool minimize(T &a, const T &b) {
  11.         if (a > b) return a = b, true;
  12.         return false;
  13.     }
  14.  
  15. template<class T>
  16.     bool maximize(T &a, const T &b) {
  17.         if (a < b) return a = b, true;
  18.         return false;
  19.     }
  20.  
  21. #define FOR(i,a,b) for(int i=(a); i<=(b); ++i)
  22. #define FORR(i,a,b) for(int i=(a); i>=(b); --i)
  23. #define REP(i, n) for(int i=0; i<(n); ++i)
  24. #define RED(i, n) for(int i=(n)-1; i>=0; --i)
  25. #define MASK(i) (1LL << (i))
  26. #define BIT(S, i) (((S) >> (i)) & 1)
  27. #define mp make_pair
  28. #define pb push_back
  29. #define fi first
  30. #define se second
  31. #define all(x) x.begin(), x.end()
  32. #define task "gen"
  33.  
  34. const int MOD = 1e9 + 7;
  35. const int inf = 1e9 + 27092008;
  36. const ll INF = 1e18 + 27092008;
  37. const int N = 200000 + 5;
  38. const int S = 350;
  39. int n, m, q, a[N];
  40. vector<int> G[N];
  41. int pos[N], timer = 0, h[N], minHigh[N << 1][20], tour[N << 1];
  42.  
  43. void dfs(int u, int par) {
  44.     pos[u] = ++timer;
  45.     tour[timer] = u;
  46.     for(int v : G[u]) if (v != par) {
  47.         h[v] = h[u] + 1;
  48.         dfs(v, u);
  49.         tour[++timer] = u;
  50.     }
  51. }
  52.  
  53. #define MIN_HIGH(x, y) (h[x] < h[y] ? x : y)
  54. int LCA(int u, int v) {
  55.     int l = pos[u], r = pos[v];
  56.     if (l > r) swap(l, r);
  57.     int k = __lg(r - l + 1);
  58.     return MIN_HIGH(minHigh[l][k], minHigh[r - MASK(k) + 1][k]);
  59. }
  60.  
  61. int dist(int u, int v) {
  62.     int p = LCA(u, v);
  63.     return h[u] + h[v] - 2 * h[p];
  64. }
  65.  
  66. ll lazy_add[N / S + 5];
  67. int lazy_set[N / S + 5], first_set[N / S + 5];
  68. ll ans[N], val[N / S + 5][N], old[N];
  69.  
  70. void rebuild(int B) {
  71.     if (lazy_set[B] == 0) return;
  72.     FOR(i, B * S, (B + 1) * S - 1) {
  73.         ans[i] += val[B][a[i]] - old[i] - dist(a[i], first_set[B]);
  74.         a[i] = lazy_set[B];
  75.         old[i] = val[B][a[i]];
  76.     }
  77.     first_set[B] = -1;
  78.     lazy_set[B] = 0;
  79. }
  80.  
  81. void init(void) {
  82.     cin >> n >> m >> q;
  83.     REP(i, m) cin >> a[i];
  84.     FOR(i, 2, n) {
  85.         int u, v;
  86.         cin >> u >> v;
  87.         G[u].pb(v);
  88.         G[v].pb(u);
  89.     }
  90. }
  91.  
  92. void process(void) {
  93.     dfs(1, -1);
  94.     FOR(i, 1, timer) minHigh[i][0] = tour[i];
  95.     FOR(j, 1, 19) FOR(i, 1, timer - MASK(j) + 1)
  96.         minHigh[i][j] = MIN_HIGH(minHigh[i][j - 1], minHigh[i + MASK(j - 1)][j - 1]);
  97.  
  98.     memset(first_set, -1, sizeof first_set);
  99.     while(q--) {
  100.         int type;
  101.         cin >> type;
  102.         if (type == 1) {
  103.             int u, v;
  104.             cin >> u >> v;
  105.             FOR(B, 0, m / S)
  106.                 if (lazy_set[B] == u)
  107.                     lazy_add[B] += v;
  108.                 else if (lazy_set[B] == 0)
  109.                     val[B][u] += v;
  110.         } else if (type == 2) {
  111.             int l, r, z;
  112.             cin >> l >> r >> z;
  113.             l--; r--;
  114.             if (l / S == r / S) {
  115.                 rebuild(l / S);
  116.                 FOR(i, l, r) {
  117.                     ans[i] += val[l / S][a[i]] - old[i] - dist(a[i], z);
  118.                     a[i] = z;
  119.                     old[i] = val[l / S][z];
  120.                 }
  121.                 continue;
  122.             }
  123.             rebuild(l / S);
  124.             rebuild(r / S);
  125.             FOR(i, l, (l / S + 1) * S - 1) {
  126.                 ans[i] += val[l / S][a[i]] - old[i] - dist(a[i], z);
  127.                 a[i] = z;
  128.                 old[i] = val[l / S][z];
  129.             }
  130.             FOR(i, (r / S) * S, r) {
  131.                 ans[i] += val[r / S][a[i]] - old[i] - dist(a[i], z);
  132.                 a[i] = z;
  133.                 old[i] = val[r / S][z];
  134.             }
  135.             FOR(i, l / S + 1, r / S - 1) {
  136.                 if (first_set[i] == -1)
  137.                     first_set[i] = z;
  138.                 if (lazy_set[i] > 0) lazy_add[i] -= dist(lazy_set[i], z);
  139.                 lazy_set[i] = z;
  140.             }
  141.         } else {
  142.             int u; cin >> u;
  143.             u--;
  144.             rebuild(u / S);
  145.             cout << ans[u] + lazy_add[u / S] + val[u / S][a[u]] - old[u] << '\n';
  146.         }
  147.     }
  148. }
  149.  
  150. signed main() {
  151.     ios_base::sync_with_stdio(0);
  152.     cin.tie(0); cout.tie(0);
  153.     if (fopen(task".inp", "r")) {
  154.         freopen(task".inp", "r", stdin);
  155.         freopen(task".out", "w", stdout);
  156.     }
  157.     int tc = 1;
  158. //    cin >> tc;
  159.     while(tc--) {
  160.         init();
  161.         process();
  162.     }
  163.     return 0;
  164. }
  165.  
Success #stdin #stdout 0.01s 12076KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/WDcKU3
language:
C++14 (gcc 8.3)
created:
3 hours 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!