/tmp/solutions/build/dynamic_tree_subtree_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|       |  i64 sum;
   10|       |  i64 sum_;
   11|       |  i64 add;
   12|       |  int size;
   13|       |  int size_;
   14|       |  int p;
   15|       |  int ch[2];
   16|       |  i8 rev;
   17|       |  i8 k;
   18|       |} node[N];
   19|       |
   20|  3.74M|def reverse(int x) -> void { node[x].rev ^= 1; }
   21|       |
   22|  8.47M|def pushdown(int x) -> void {
   23|  8.47M|  if (node[x].rev) {
  ------------------
  |  Branch (23:7): [True: 20.50%, False: 79.50%]
  ------------------
   24|  1.73M|    std::swap(node[x].ch[0], node[x].ch[1]);
   25|  1.73M|    node[node[x].ch[0]].k = 0;
   26|  1.73M|    node[node[x].ch[1]].k = 1;
   27|  1.73M|    reverse(node[x].ch[0]);
   28|  1.73M|    reverse(node[x].ch[1]);
   29|  1.73M|    node[x].rev = 0;
   30|  1.73M|  }
   31|  8.47M|}
   32|       |
   33|  8.05M|def maintain(int x) -> void {
   34|  8.05M|  node[x].size =
   35|  8.05M|      node[node[x].ch[0]].size + 1 + node[node[x].ch[1]].size + node[x].size_;
   36|  8.05M|  node[x].sum = node[node[x].ch[0]].sum + node[node[x].ch[1]].sum +
   37|  8.05M|                node[x].sum_ + node[x].size * node[x].add;
   38|  8.05M|}
   39|       |
   40|  5.62M|def rotateup(int x) -> void {
   41|  5.62M|  int p = node[x].p;
   42|  5.62M|  int g = node[p].p;
   43|  5.62M|  int k = node[x].k;
   44|  5.62M|  int t = node[p].k;
   45|  5.62M|  i64 b = node[x].add;
   46|  5.62M|  i64 a = node[p].add;
   47|  5.62M|  node[x].add = a + b;
   48|  5.62M|  node[p].add = -b;
   49|  5.62M|  node[node[x].ch[k ^ 1]].add += b;
   50|  5.62M|  node[node[x].ch[k ^ 1]].sum += b * node[node[x].ch[k ^ 1]].size;
   51|  5.62M|  node[node[x].ch[k ^ 1]].p = p;
   52|  5.62M|  node[node[x].ch[k ^ 1]].k = k;
   53|  5.62M|  node[p].ch[k] = node[x].ch[k ^ 1];
   54|  5.62M|  node[p].p = x;
   55|  5.62M|  node[p].k = k ^ 1;
   56|  5.62M|  node[x].ch[k ^ 1] = p;
   57|  5.62M|  node[x].p = g;
   58|  5.62M|  node[x].k = t;
   59|  5.62M|  if (t != -1) {
  ------------------
  |  Branch (59:7): [True: 36.10%, False: 63.90%]
  ------------------
   60|  2.03M|    node[g].ch[t] = x;
   61|  2.03M|  }
   62|  5.62M|  maintain(p);
   63|  5.62M|}
   64|       |
   65|  7.05M|def is_root(int x) -> bool { return node[x].k == -1; }
   66|       |
   67|  2.42M|def splay(int x) -> void {
   68|  2.42M|  pushdown(x);
   69|  4.73M|  while (!is_root(x)) {
  ------------------
  |  Branch (69:10): [True: 48.88%, False: 51.12%]
  ------------------
   70|  2.31M|    if (int p = node[x].p; is_root(p)) {
  ------------------
  |  Branch (70:28): [True: 38.50%, False: 61.50%]
  ------------------
   71|   891k|      pushdown(p);
   72|   891k|      pushdown(x);
   73|   891k|      rotateup(x);
   74|  1.42M|    } else {
   75|  1.42M|      int g = node[p].p;
   76|  1.42M|      pushdown(g);
   77|  1.42M|      pushdown(p);
   78|  1.42M|      pushdown(x);
   79|  1.42M|      if (node[x].k == node[p].k) {
  ------------------
  |  Branch (79:11): [True: 57.51%, False: 42.49%]
  ------------------
   80|   818k|        rotateup(p);
   81|   818k|        rotateup(x);
   82|   818k|      } else {
   83|   605k|        rotateup(x);
   84|   605k|        rotateup(x);
   85|   605k|      }
   86|  1.42M|    }
   87|  2.31M|  }
   88|  2.42M|}
   89|       |
   90|   532k|def access(int x) -> void {
   91|   532k|  splay(x);
   92|   532k|  node[node[x].ch[1]].k = -1;
   93|   532k|  node[x].sum_ += node[node[x].ch[1]].sum;
   94|   532k|  node[x].size_ += node[node[x].ch[1]].size;
   95|   532k|  node[x].ch[1] = 0;
   96|   532k|  maintain(x);
   97|  2.42M|  while (int p = node[x].p) {
  ------------------
  |  Branch (97:14): [True: 78.00%, False: 22.00%]
  ------------------
   98|  1.88M|    splay(p);
   99|  1.88M|    node[node[p].ch[1]].k = -1;
  100|  1.88M|    node[p].sum_ += node[node[p].ch[1]].sum;
  101|  1.88M|    node[p].size_ += node[node[p].ch[1]].size;
  102|  1.88M|    node[p].sum_ -= node[x].sum;
  103|  1.88M|    node[p].size_ -= node[x].size;
  104|  1.88M|    node[p].ch[1] = x;
  105|  1.88M|    node[x].k = 1;
  106|  1.88M|    rotateup(x);
  107|  1.88M|    maintain(x);
  108|  1.88M|  }
  109|   532k|}
  110|       |
  111|       |int head[N];
  112|       |struct {
  113|       |  int to;
  114|       |  int next;
  115|       |} edge[N * 2];
  116|       |
  117|   200k|def build(int u, int p) -> void {
  118|   599k|  for (int e = head[u]; e; e = edge[e].next) {
                                         ^399k
  ------------------
  |  Branch (118:25): [True: 66.67%, False: 33.33%]
  ------------------
  119|   399k|    int v = edge[e].to;
  120|   399k|    if (v != p) {
  ------------------
  |  Branch (120:9): [True: 50.00%, False: 50.00%]
  ------------------
  121|   199k|      build(v, u);
  122|   199k|      node[v + 1].p = u + 1;
  123|   199k|      node[u + 1].sum_ += node[v + 1].sum;
  124|   199k|      node[u + 1].size_ += node[v + 1].size;
  125|   199k|    }
  126|   399k|  }
  127|   200k|  node[u + 1].sum = node[u + 1].sum_;
  128|   200k|  node[u + 1].size = node[u + 1].size_ + 1;
  129|   200k|}
  130|       |
  131|       |} // namespace
  132|       |
  133|      1|int main() {
  134|      1|  rd rd;
  135|      1|  wt wt;
  136|      1|  int n = rd.uh();
  137|      1|  int q = rd.uh();
  138|      1|#ifdef LOCAL
  139|      1|  std::memset(head, 0, 4 * n);
  140|      1|#endif
  141|   200k|  for (int i = 1; i <= n; ++i) node[i] = {.sum_ = rd.uw(), .k = -1};
                                        ^200k^200k
  ------------------
  |  Branch (141:19): [True: 100.00%, False: 0.00%]
  ------------------
  142|   200k|  for (int i = 1; i != n; ++i) {
                                        ^199k
  ------------------
  |  Branch (142:19): [True: 100.00%, False: 0.00%]
  ------------------
  143|   199k|    int u = rd.uh();
  144|   199k|    int v = rd.uh();
  145|   199k|    edge[i * 2 | 0] = {v, head[u]}, head[u] = i * 2 | 0;
  146|   199k|    edge[i * 2 | 1] = {u, head[v]}, head[v] = i * 2 | 1;
  147|   199k|  }
  148|      1|  build(0, 0);
  149|   200k|  while (q--) {
  ------------------
  |  Branch (149:10): [True: 100.00%, False: 0.00%]
  ------------------
  150|   200k|    let t = rd.u1();
  151|   200k|    if (t == 0) {
  ------------------
  |  Branch (151:9): [True: 33.19%, False: 66.81%]
  ------------------
  152|  66.3k|      int u = rd.uh() + 1;
  153|  66.3k|      int v = rd.uh() + 1;
  154|  66.3k|      access(u);
  155|  66.3k|      reverse(u);
  156|  66.3k|      access(v);
  157|  66.3k|      node[node[v].ch[0]].p = 0;
  158|  66.3k|      node[node[v].ch[0]].k = -1;
  159|  66.3k|      node[node[v].ch[0]].add += node[v].add;
  160|  66.3k|      node[v].ch[0] = 0;
  161|  66.3k|      int w = rd.uh() + 1;
  162|  66.3k|      int x = rd.uh() + 1;
  163|  66.3k|      access(w);
  164|  66.3k|      reverse(w);
  165|  66.3k|      access(x);
  166|  66.3k|      node[w].p = x;
  167|  66.3k|      node[w].add -= node[x].add;
  168|  66.3k|      node[w].sum -= node[x].add * node[w].size;
  169|  66.3k|      node[x].sum_ += node[w].sum;
  170|  66.3k|      node[x].size_ += node[w].size;
  171|  66.3k|    }
  172|   200k|    if (t == 1) {
  ------------------
  |  Branch (172:9): [True: 33.40%, False: 66.60%]
  ------------------
  173|  66.7k|      int u = rd.uh() + 1;
  174|  66.7k|      int p = rd.uh() + 1;
  175|  66.7k|      i64 x = rd.uw();
  176|  66.7k|      access(u);
  177|  66.7k|      reverse(u);
  178|  66.7k|      access(p);
  179|  66.7k|      node[u].add += x;
  180|  66.7k|      node[u].sum += x * node[u].size;
  181|  66.7k|    }
  182|   200k|    if (t == 2) {
  ------------------
  |  Branch (182:9): [True: 33.41%, False: 66.59%]
  ------------------
  183|  66.8k|      int u = rd.uh() + 1;
  184|  66.8k|      int p = rd.uh() + 1;
  185|  66.8k|      access(u);
  186|  66.8k|      reverse(u);
  187|  66.8k|      access(p);
  188|  66.8k|      i64 ans = node[u].sum + node[u].size * node[p].add;
  189|  66.8k|      wt.ud(ans);
  190|  66.8k|    }
  191|   200k|  }
  192|      1|  return 0;
  193|      1|}