/tmp/solutions/build/lca-fast.cpp:
    1|       |#include <common.h>
    2|       |#include <toy/bit.h>
    3|       |prelude;
    4|       |
    5|       |namespace {
    6|       |
    7|       |constexpr int N = 5e5;
    8|       |
    9|       |int parent[N];
   10|       |int node2id[N];
   11|       |int id2node[N];
   12|       |
   13|       |} // namespace
   14|       |
   15|      1|int main() {
   16|      1|  rd rd;
   17|      1|  wt wt;
   18|      1|  int n = rd.uh();
   19|      1|  int q = rd.uh();
   20|      1|#ifdef LOCAL
   21|      1|  std::memset(node2id, 0, 4 * n);
   22|      1|#endif
   23|      5|  for (int i = 1; i < n; ++i) parent[i] = rd.uh();
                                       ^4   ^4
  ------------------
  |  Branch (23:19): [True: 80.00%, False: 20.00%]
  ------------------
   24|      5|  for (int i = n - 1; i > 0; --i) node2id[parent[i]] += node2id[i] + 1;
                                           ^4   ^4
  ------------------
  |  Branch (24:23): [True: 80.00%, False: 20.00%]
  ------------------
   25|      5|  for (int i = 1; i < n; ++i) {
                                       ^4
  ------------------
  |  Branch (25:19): [True: 80.00%, False: 20.00%]
  ------------------
   26|      4|    int p = parent[i];
   27|      4|    int &u = node2id[i];
   28|      4|    int &w = node2id[p];
   29|      4|    int t = w - u - 1;
   30|      4|    u = w, w = t;
   31|      4|  }
   32|      5|  for (int i = 1; i < n; ++i) id2node[node2id[i]] = parent[i];
                                       ^4   ^4
  ------------------
  |  Branch (32:19): [True: 80.00%, False: 20.00%]
  ------------------
   33|      1|  int m = n / 64 + 1;
   34|      1|  int len = log(m) + 1;
   35|      1|  int table[len][m];
   36|      1|  int suf[n];
   37|      1|  int pre[n];
   38|      6|  for (int min, i = 0; i < n; ++i) {
                                            ^5
  ------------------
  |  Branch (38:24): [True: 83.33%, False: 16.67%]
  ------------------
   39|      5|    int id = i & 63;
   40|      5|    int value = pre[i] = id2node[i];
   41|      5|    suf[i] = min = id ? std::min(min, value) : value;
                                      ^4                     ^1
  ------------------
  |  Branch (41:20): [True: 80.00%, False: 20.00%]
  ------------------
   42|      5|    if (id == 63) table[0][i / 64] = suf[i];
                                ^0
  ------------------
  |  Branch (42:9): [True: 0.00%, False: 100.00%]
  ------------------
   43|      5|  }
   44|      5|  for (int min, i = n - 2; i >= 0; --i) {
                                                 ^4
  ------------------
  |  Branch (44:28): [True: 80.00%, False: 20.00%]
  ------------------
   45|      4|    int id = ~i & 63;
   46|      4|    int value = pre[i];
   47|      4|    pre[i] = min = id ? std::min(min, value) : value;
                                                             ^0
  ------------------
  |  Branch (47:20): [True: 100.00%, False: 0.00%]
  ------------------
   48|      4|  }
   49|      1|  for (int i = 1; i < len; ++i) {
                                         ^0
  ------------------
  |  Branch (49:19): [True: 0.00%, False: 100.00%]
  ------------------
   50|      0|    for (int j = 0, k = 1 << (i - 1); k < m; ++j, ++k) {
  ------------------
  |  Branch (50:39): [True: 0.00%, False: 0.00%]
  ------------------
   51|      0|      table[i][j] = std::min(table[i - 1][j], table[i - 1][k]);
   52|      0|    }
   53|      0|  }
   54|      6|  while (q--) {
  ------------------
  |  Branch (54:10): [True: 83.33%, False: 16.67%]
  ------------------
   55|      5|    int u = node2id[rd.uh()];
   56|      5|    int v = node2id[rd.uh()];
   57|      5|    int l = std::min(u, v) + 1;
   58|      5|    int r = std::max(u, v);
   59|      5|    int L = l / 64;
   60|      5|    int R = r / 64;
   61|      5|    int w;
   62|      5|    if (L < R - 1) {
  ------------------
  |  Branch (62:9): [True: 0.00%, False: 100.00%]
  ------------------
   63|      0|      int p = pre[l];
   64|      0|      int s = suf[r];
   65|      0|      w = std::min(p, s);
   66|      0|      int k = log(R - L - 1);
   67|      0|      int a = table[k][L + 1];
   68|      0|      int b = table[k][R - (1 << k)];
   69|      0|      int tmp = std::min(a, b);
   70|      0|      w = std::min(w, tmp);
   71|      5|    } else if (L == R - 1) {
  ------------------
  |  Branch (71:16): [True: 0.00%, False: 100.00%]
  ------------------
   72|      0|      int p = pre[l];
   73|      0|      int s = suf[r];
   74|      0|      w = std::min(p, s);
   75|      5|    } else {
   76|      5|      w = id2node[l];
   77|     12|      for (int i = l + 1; i <= r; ++i) w = std::min(w, id2node[i]);
                                                ^7   ^7
  ------------------
  |  Branch (77:27): [True: 58.33%, False: 41.67%]
  ------------------
   78|      5|    }
   79|      5|    wt.uw(w);
   80|      5|  }
   81|      1|  return 0;
   82|      1|}