/tmp/solutions/build/vertex_add_subtree_sum-main.cpp:
    1|       |#include <common.h>
    2|       |prelude;
    3|       |
    4|       |namespace {
    5|       |
    6|       |constexpr int N = 5e5;
    7|       |
    8|       |int a[N];
    9|       |int p[N];
   10|       |int l[N];
   11|       |u64 b[N + 1];
   12|       |
   13|       |} // namespace
   14|       |
   15|     16|int main() {
   16|     16|  rd rd;
   17|     16|  wt wt;
   18|     16|  int n = rd.uh();
   19|     16|  int q = rd.uh();
   20|     16|#ifdef LOCAL
   21|     16|  std::memset(l, 0, 4 * n);
   22|     16|#endif
   23|  4.11M|  for (int i = 0; i < n; ++i) a[i] = rd.uw();
                                       ^4.11M^4.11M
  ------------------
  |  Branch (23:19): [True: 100.00%, False: 0.00%]
  ------------------
   24|  4.11M|  for (int i = 1; i < n; ++i) p[i] = rd.uh();
                                       ^4.11M^4.11M
  ------------------
  |  Branch (24:19): [True: 100.00%, False: 0.00%]
  ------------------
   25|  4.11M|  for (int i = n - 1; i > 0; --i) l[p[i]] += (l[i] += 1);
                                           ^4.11M^4.11M
  ------------------
  |  Branch (25:23): [True: 100.00%, False: 0.00%]
  ------------------
   26|     16|  l[0] = p[0] = n;
   27|  4.11M|  for (int i = 1; i < n; ++i) {
                                       ^4.11M
  ------------------
  |  Branch (27:19): [True: 100.00%, False: 0.00%]
  ------------------
   28|  4.11M|    int j = p[i];
   29|  4.11M|    int li = l[i];
   30|  4.11M|    int lj = l[j];
   31|  4.11M|    l[i] = p[i] = lj;
   32|  4.11M|    l[j] -= li;
   33|  4.11M|  }
   34|  4.11M|  for (int i = 0; i < n; ++i) b[l[i]] = a[i];
                                       ^4.11M^4.11M
  ------------------
  |  Branch (34:19): [True: 100.00%, False: 0.00%]
  ------------------
   35|  4.11M|  for (int i = 1; i <= n; ++i) b[i] += b[i - 1];
                                        ^4.11M^4.11M
  ------------------
  |  Branch (35:19): [True: 100.00%, False: 0.00%]
  ------------------
   36|  4.11M|  for (int i = n; i >= 1; --i) b[i] -= b[i - (i & -i)];
                                        ^4.11M^4.11M
  ------------------
  |  Branch (36:19): [True: 100.00%, False: 0.00%]
  ------------------
   37|  3.83M|  while (q--) {
  ------------------
  |  Branch (37:10): [True: 100.00%, False: 0.00%]
  ------------------
   38|  3.83M|    let t = rd.u1();
   39|  3.83M|    if (t == 0) {
  ------------------
  |  Branch (39:9): [True: 50.03%, False: 49.97%]
  ------------------
   40|  1.91M|      int k = l[rd.uh()];
   41|  1.91M|      int x = rd.uw();
   42|  20.0M|      for (; k <= n; k += k & -k) b[k] += x;
                                   ^18.1M       ^18.1M
  ------------------
  |  Branch (42:14): [True: 90.44%, False: 9.56%]
  ------------------
   43|  1.91M|    }
   44|  3.83M|    if (t == 1) {
  ------------------
  |  Branch (44:9): [True: 49.97%, False: 50.03%]
  ------------------
   45|  1.91M|      int x = rd.uh();
   46|  1.91M|      int L = l[x] - 1;
   47|  1.91M|      int R = p[x];
   48|  1.91M|      u64 sum = 0;
   49|  19.4M|      for (; L > 0; L -= L & -L) sum -= b[L];
                                  ^17.5M       ^17.5M
  ------------------
  |  Branch (49:14): [True: 90.16%, False: 9.84%]
  ------------------
   50|  18.2M|      for (; R > 0; R -= R & -R) sum += b[R];
                                  ^16.3M       ^16.3M
  ------------------
  |  Branch (50:14): [True: 89.51%, False: 10.49%]
  ------------------
   51|  1.91M|      wt.ud(sum);
   52|  1.91M|    }
   53|  3.83M|  }
   54|     16|  return 0;
   55|     16|}