/tmp/solutions/build/dynamic_tree_vertex_add_path_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|       |  int p;
   12|       |  int ch[2];
   13|       |  i8 rev;
   14|       |  i8 k;
   15|       |} node[N];
   16|       |
   17|  10.3M|def reverse(int x) -> void { node[x].rev ^= 1; }
   18|       |
   19|  12.1M|def pushdown(int x) -> void {
   20|  12.1M|  if (node[x].rev) {
  ------------------
  |  Branch (20:7): [True: 41.68%, False: 58.32%]
  ------------------
   21|  5.07M|    std::swap(node[x].ch[0], node[x].ch[1]);
   22|  5.07M|    node[node[x].ch[0]].k = 0;
   23|  5.07M|    node[node[x].ch[1]].k = 1;
   24|  5.07M|    reverse(node[x].ch[0]);
   25|  5.07M|    reverse(node[x].ch[1]);
   26|  5.07M|    node[x].rev = 0;
   27|  5.07M|  }
   28|  12.1M|}
   29|       |
   30|  7.96M|def maintain(int x) -> void {
   31|  7.96M|  node[x].sum = node[node[x].ch[0]].sum + node[x].val + node[node[x].ch[1]].sum;
   32|  7.96M|}
   33|       |
   34|  7.96M|def rotateup(int x) -> void {
   35|  7.96M|  int p = node[x].p;
   36|  7.96M|  int g = node[p].p;
   37|  7.96M|  int k = node[x].k;
   38|  7.96M|  int t = node[p].k;
   39|  7.96M|  node[node[x].ch[k ^ 1]].p = p;
   40|  7.96M|  node[node[x].ch[k ^ 1]].k = k;
   41|  7.96M|  node[p].ch[k] = node[x].ch[k ^ 1];
   42|  7.96M|  node[p].p = x;
   43|  7.96M|  node[p].k = k ^ 1;
   44|  7.96M|  node[x].ch[k ^ 1] = p;
   45|  7.96M|  node[x].p = g;
   46|  7.96M|  node[x].k = t;
   47|  7.96M|  if (t != -1) {
  ------------------
  |  Branch (47:7): [True: 85.60%, False: 14.40%]
  ------------------
   48|  6.81M|    node[g].ch[t] = x;
   49|  6.81M|  }
   50|  7.96M|  maintain(p);
   51|  7.96M|}
   52|       |
   53|  8.63M|def is_root(int x) -> bool { return node[x].k == -1; }
   54|       |
   55|  1.00M|def splay(int x) -> void {
   56|  1.00M|  pushdown(x);
   57|  4.81M|  while (!is_root(x)) {
  ------------------
  |  Branch (57:10): [True: 79.24%, False: 20.76%]
  ------------------
   58|  3.81M|    if (int p = node[x].p; is_root(p)) {
  ------------------
  |  Branch (58:28): [True: 7.26%, False: 92.74%]
  ------------------
   59|   277k|      pushdown(p);
   60|   277k|      pushdown(x);
   61|   277k|      rotateup(x);
   62|  3.54M|    } else {
   63|  3.54M|      int g = node[p].p;
   64|  3.54M|      pushdown(g);
   65|  3.54M|      pushdown(p);
   66|  3.54M|      pushdown(x);
   67|  3.54M|      if (node[x].k == node[p].k) {
  ------------------
  |  Branch (67:11): [True: 55.91%, False: 44.09%]
  ------------------
   68|  1.98M|        rotateup(p);
   69|  1.98M|        rotateup(x);
   70|  1.98M|      } else {
   71|  1.56M|        rotateup(x);
   72|  1.56M|        rotateup(x);
   73|  1.56M|      }
   74|  3.54M|    }
   75|  3.81M|  }
   76|  1.00M|}
   77|       |
   78|   333k|def access(int x) -> void {
   79|   333k|  splay(x);
   80|   333k|  node[node[x].ch[1]].k = -1;
   81|   333k|  node[x].ch[1] = 0;
   82|   934k|  while (int p = node[x].p) {
  ------------------
  |  Branch (82:14): [True: 64.26%, False: 35.74%]
  ------------------
   83|   600k|    splay(p);
   84|   600k|    node[node[p].ch[1]].k = -1;
   85|   600k|    node[p].ch[1] = x;
   86|   600k|    node[x].k = 1;
   87|   600k|    rotateup(x);
   88|   600k|  }
   89|   333k|}
   90|       |
   91|       |int head[N];
   92|       |struct {
   93|       |  int to;
   94|       |  int next;
   95|       |} edge[N * 2];
   96|       |
   97|   200k|def build(int u, int p) -> void {
   98|   599k|  for (int e = head[u]; e; e = edge[e].next) {
                                         ^399k
  ------------------
  |  Branch (98:25): [True: 66.67%, False: 33.33%]
  ------------------
   99|   399k|    int v = edge[e].to;
  100|   399k|    if (v != p) {
  ------------------
  |  Branch (100:9): [True: 50.00%, False: 50.00%]
  ------------------
  101|   199k|      build(v, u);
  102|   199k|      node[v + 1].p = u + 1;
  103|   199k|    }
  104|   399k|  }
  105|   200k|}
  106|       |
  107|       |} // namespace
  108|       |
  109|      1|int main() {
  110|      1|  rd rd;
  111|      1|  wt wt;
  112|      1|  int n = rd.uh();
  113|      1|  int q = rd.uh();
  114|      1|#ifdef LOCAL
  115|      1|  std::memset(head, 0, 4 * n);
  116|      1|#endif
  117|   200k|  for (int i = 1; i <= n; ++i)
                                        ^200k
  ------------------
  |  Branch (117:19): [True: 100.00%, False: 0.00%]
  ------------------
  118|   200k|    node[i] = {.k = -1}, node[i].sum = node[i].val = rd.uw();
  119|   200k|  for (int i = 1; i != n; ++i) {
                                        ^199k
  ------------------
  |  Branch (119:19): [True: 100.00%, False: 0.00%]
  ------------------
  120|   199k|    int u = rd.uh();
  121|   199k|    int v = rd.uh();
  122|   199k|    edge[i * 2 | 0] = {v, head[u]}, head[u] = i * 2 | 0;
  123|   199k|    edge[i * 2 | 1] = {u, head[v]}, head[v] = i * 2 | 1;
  124|   199k|  }
  125|      1|  build(0, 0);
  126|   200k|  while (q--) {
  ------------------
  |  Branch (126:10): [True: 100.00%, False: 0.00%]
  ------------------
  127|   200k|    let t = rd.u1();
  128|   200k|    if (t == 0) {
  ------------------
  |  Branch (128:9): [True: 33.52%, False: 66.48%]
  ------------------
  129|  67.0k|      int u = rd.uh() + 1;
  130|  67.0k|      int v = rd.uh() + 1;
  131|  67.0k|      access(u);
  132|  67.0k|      reverse(u);
  133|  67.0k|      access(v);
  134|  67.0k|      node[node[v].ch[0]].p = 0;
  135|  67.0k|      node[node[v].ch[0]].k = -1;
  136|  67.0k|      node[v].ch[0] = 0;
  137|  67.0k|      int w = rd.uh() + 1;
  138|  67.0k|      int x = rd.uh() + 1;
  139|  67.0k|      access(w);
  140|  67.0k|      reverse(w);
  141|  67.0k|      node[w].p = x;
  142|  67.0k|    }
  143|   200k|    if (t == 1) {
  ------------------
  |  Branch (143:9): [True: 33.30%, False: 66.70%]
  ------------------
  144|  66.5k|      int u = rd.uh() + 1;
  145|  66.5k|      u32 x = rd.uw();
  146|  66.5k|      splay(u);
  147|  66.5k|      node[u].val += x;
  148|  66.5k|      node[u].sum += x;
  149|  66.5k|    }
  150|   200k|    if (t == 2) {
  ------------------
  |  Branch (150:9): [True: 33.18%, False: 66.82%]
  ------------------
  151|  66.3k|      int u = rd.uh() + 1;
  152|  66.3k|      int v = rd.uh() + 1;
  153|  66.3k|      access(u);
  154|  66.3k|      reverse(u);
  155|  66.3k|      access(v);
  156|  66.3k|      wt.ud(node[node[v].ch[0]].sum + node[v].val);
  157|  66.3k|    }
  158|   200k|  }
  159|      1|  return 0;
  160|      1|}