/tmp/solutions/build/dynamic_tree_vertex_add_subtree_sum-main.cpp:
    1|       |#include <common.h>
    2|       |prelude;
    3|       |
    4|       |namespace {
    5|       |
    6|       |constexpr int N = 200001;
    7|       |
    8|       |struct Node {
    9|       |  u64 val;
   10|       |  u64 sum;
   11|       |  u64 sum_;
   12|       |  int p;
   13|       |  int ch[2];
   14|       |  i8 rev;
   15|       |  i8 k;
   16|       |} node[N];
   17|       |
   18|  45.0M|def reverse(int x) -> void { node[x].rev ^= 1; }
   19|       |
   20|  82.6M|def pushdown(int x) -> void {
   21|  82.6M|  if (node[x].rev) {
  ------------------
  |  Branch (21:7): [True: 26.04%, False: 73.96%]
  ------------------
   22|  21.5M|    std::swap(node[x].ch[0], node[x].ch[1]);
   23|  21.5M|    node[node[x].ch[0]].k = 0;
   24|  21.5M|    node[node[x].ch[1]].k = 1;
   25|  21.5M|    reverse(node[x].ch[0]);
   26|  21.5M|    reverse(node[x].ch[1]);
   27|  21.5M|    node[x].rev = 0;
   28|  21.5M|  }
   29|  82.6M|}
   30|       |
   31|  74.2M|def maintain(int x) -> void {
   32|  74.2M|  node[x].sum = node[node[x].ch[0]].sum + node[x].val +
   33|  74.2M|                node[node[x].ch[1]].sum + node[x].sum_;
   34|  74.2M|}
   35|       |
   36|  54.7M|def rotateup(int x) -> void {
   37|  54.7M|  int p = node[x].p;
   38|  54.7M|  int g = node[p].p;
   39|  54.7M|  int k = node[x].k;
   40|  54.7M|  int t = node[p].k;
   41|  54.7M|  node[node[x].ch[k ^ 1]].p = p;
   42|  54.7M|  node[node[x].ch[k ^ 1]].k = k;
   43|  54.7M|  node[p].ch[k] = node[x].ch[k ^ 1];
   44|  54.7M|  node[p].p = x;
   45|  54.7M|  node[p].k = k ^ 1;
   46|  54.7M|  node[x].ch[k ^ 1] = p;
   47|  54.7M|  node[x].p = g;
   48|  54.7M|  node[x].k = t;
   49|  54.7M|  if (t != -1) {
  ------------------
  |  Branch (49:7): [True: 48.15%, False: 51.85%]
  ------------------
   50|  26.3M|    node[g].ch[t] = x;
   51|  26.3M|  }
   52|  54.7M|  maintain(p);
   53|  54.7M|}
   54|       |
   55|  66.2M|def is_root(int x) -> bool { return node[x].k == -1; }
   56|       |
   57|  19.5M|def splay(int x) -> void {
   58|  19.5M|  pushdown(x);
   59|  42.8M|  while (!is_root(x)) {
  ------------------
  |  Branch (59:10): [True: 54.52%, False: 45.48%]
  ------------------
   60|  23.3M|    if (int p = node[x].p; is_root(p)) {
  ------------------
  |  Branch (60:28): [True: 29.86%, False: 70.14%]
  ------------------
   61|  6.98M|      pushdown(p);
   62|  6.98M|      pushdown(x);
   63|  6.98M|      rotateup(x);
   64|  16.4M|    } else {
   65|  16.4M|      int g = node[p].p;
   66|  16.4M|      pushdown(g);
   67|  16.4M|      pushdown(p);
   68|  16.4M|      pushdown(x);
   69|  16.4M|      if (node[x].k == node[p].k) {
  ------------------
  |  Branch (69:11): [True: 55.72%, False: 44.28%]
  ------------------
   70|  9.14M|        rotateup(p);
   71|  9.14M|        rotateup(x);
   72|  9.14M|      } else {
   73|  7.26M|        rotateup(x);
   74|  7.26M|        rotateup(x);
   75|  7.26M|      }
   76|  16.4M|    }
   77|  23.3M|  }
   78|  19.5M|}
   79|       |
   80|  4.54M|def access(int x) -> void {
   81|  4.54M|  splay(x);
   82|  4.54M|  node[node[x].ch[1]].k = -1;
   83|  4.54M|  node[x].sum_ += node[node[x].ch[1]].sum;
   84|  4.54M|  node[x].ch[1] = 0;
   85|  4.54M|  maintain(x);
   86|  19.5M|  while (int p = node[x].p) {
  ------------------
  |  Branch (86:14): [True: 76.69%, False: 23.31%]
  ------------------
   87|  14.9M|    splay(p);
   88|  14.9M|    node[node[p].ch[1]].k = -1;
   89|  14.9M|    node[p].sum_ += node[node[p].ch[1]].sum;
   90|  14.9M|    node[p].sum_ -= node[x].sum;
   91|  14.9M|    node[p].ch[1] = x;
   92|  14.9M|    node[x].k = 1;
   93|  14.9M|    rotateup(x);
   94|  14.9M|    maintain(x);
   95|  14.9M|  }
   96|  4.54M|}
   97|       |
   98|       |int head[N];
   99|       |struct {
  100|       |  int to;
  101|       |  int next;
  102|       |} edge[N * 2];
  103|       |
  104|  1.91M|def build(int u, int p) -> void {
  105|  5.75M|  for (int e = head[u]; e; e = edge[e].next) {
                                         ^3.83M
  ------------------
  |  Branch (105:25): [True: 66.67%, False: 33.33%]
  ------------------
  106|  3.83M|    int v = edge[e].to;
  107|  3.83M|    if (v != p) {
  ------------------
  |  Branch (107:9): [True: 50.00%, False: 50.00%]
  ------------------
  108|  1.91M|      build(v, u);
  109|  1.91M|      node[v + 1].p = u + 1;
  110|  1.91M|      node[u + 1].sum_ += node[v + 1].sum;
  111|  1.91M|    }
  112|  3.83M|  }
  113|  1.91M|  node[u + 1].sum = node[u + 1].val + node[u + 1].sum_;
  114|  1.91M|}
  115|       |
  116|       |} // namespace
  117|       |
  118|     18|int main() {
  119|     18|  rd rd;
  120|     18|  wt wt;
  121|     18|  int n = rd.uh();
  122|     18|  int q = rd.uh();
  123|     18|#ifdef LOCAL
  124|     18|  std::memset(head, 0, 4 * n);
  125|     18|#endif
  126|  1.91M|  for (int i = 1; i <= n; ++i) node[i] = {.val = rd.uw(), .k = -1};
                                        ^1.91M^1.91M
  ------------------
  |  Branch (126:19): [True: 100.00%, False: 0.00%]
  ------------------
  127|  1.91M|  for (int i = 1; i != n; ++i) {
                                        ^1.91M
  ------------------
  |  Branch (127:19): [True: 100.00%, False: 0.00%]
  ------------------
  128|  1.91M|    int u = rd.uh();
  129|  1.91M|    int v = rd.uh();
  130|  1.91M|    edge[i * 2 | 0] = {v, head[u]}, head[u] = i * 2 | 0;
  131|  1.91M|    edge[i * 2 | 1] = {u, head[v]}, head[v] = i * 2 | 1;
  132|  1.91M|  }
  133|     18|  build(0, 0);
  134|  1.94M|  while (q--) {
  ------------------
  |  Branch (134:10): [True: 100.00%, False: 0.00%]
  ------------------
  135|  1.94M|    let t = rd.u1();
  136|  1.94M|    if (t == 0) {
  ------------------
  |  Branch (136:9): [True: 33.38%, False: 66.62%]
  ------------------
  137|   650k|      int u = rd.uh() + 1;
  138|   650k|      int v = rd.uh() + 1;
  139|   650k|      access(u);
  140|   650k|      reverse(u);
  141|   650k|      access(v);
  142|   650k|      node[node[v].ch[0]].p = 0;
  143|   650k|      node[node[v].ch[0]].k = -1;
  144|   650k|      node[v].ch[0] = 0;
  145|   650k|      int w = rd.uh() + 1;
  146|   650k|      int x = rd.uh() + 1;
  147|   650k|      access(w);
  148|   650k|      reverse(w);
  149|   650k|      access(x);
  150|   650k|      node[w].p = x;
  151|   650k|      node[x].sum_ += node[w].sum;
  152|   650k|    }
  153|  1.94M|    if (t == 1) {
  ------------------
  |  Branch (153:9): [True: 33.31%, False: 66.69%]
  ------------------
  154|   648k|      int u = rd.uh() + 1;
  155|   648k|      u32 x = rd.uw();
  156|   648k|      access(u);
  157|   648k|      node[u].val += x;
  158|   648k|    }
  159|  1.94M|    if (t == 2) {
  ------------------
  |  Branch (159:9): [True: 33.31%, False: 66.69%]
  ------------------
  160|   648k|      int u = rd.uh() + 1;
  161|   648k|      int p = rd.uh() + 1;
  162|   648k|      access(u);
  163|   648k|      reverse(u);
  164|   648k|      access(p);
  165|   648k|      wt.ud(node[u].sum);
  166|   648k|    }
  167|  1.94M|  }
  168|     18|  return 0;
  169|     18|}