/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|     25|int main() {
   16|     25|  rd rd;
   17|     25|  wt wt;
   18|     25|  int n = rd.uh();
   19|     25|  int q = rd.uh();
   20|     25|#ifdef LOCAL
   21|     25|  std::memset(node2id, 0, 4 * n);
   22|     25|#endif
   23|  10.2M|  for (int i = 1; i < n; ++i) parent[i] = rd.uh();
                                       ^10.2M^10.2M
  ------------------
  |  Branch (23:19): [True: 100.00%, False: 0.00%]
  ------------------
   24|  10.2M|  for (int i = n - 1; i > 0; --i) node2id[parent[i]] += node2id[i] + 1;
                                           ^10.2M^10.2M
  ------------------
  |  Branch (24:23): [True: 100.00%, False: 0.00%]
  ------------------
   25|  10.2M|  for (int i = 1; i < n; ++i) {
                                       ^10.2M
  ------------------
  |  Branch (25:19): [True: 100.00%, False: 0.00%]
  ------------------
   26|  10.2M|    int p = parent[i];
   27|  10.2M|    int &u = node2id[i];
   28|  10.2M|    int &w = node2id[p];
   29|  10.2M|    int t = w - u - 1;
   30|  10.2M|    u = w, w = t;
   31|  10.2M|  }
   32|  10.2M|  for (int i = 1; i < n; ++i) id2node[node2id[i]] = parent[i];
                                       ^10.2M^10.2M
  ------------------
  |  Branch (32:19): [True: 100.00%, False: 0.00%]
  ------------------
   33|     25|  int m = n / 64 + 1;
   34|     25|  int len = log(m) + 1;
   35|     25|  int table[len][m];
   36|     25|  int suf[n];
   37|     25|  int pre[n];
   38|  10.2M|  for (int min, i = 0; i < n; ++i) {
                                            ^10.2M
  ------------------
  |  Branch (38:24): [True: 100.00%, False: 0.00%]
  ------------------
   39|  10.2M|    int id = i & 63;
   40|  10.2M|    int value = pre[i] = id2node[i];
   41|  10.2M|    suf[i] = min = id ? std::min(min, value) : value;
                                      ^10.0M                 ^159k
  ------------------
  |  Branch (41:20): [True: 98.44%, False: 1.56%]
  ------------------
   42|  10.2M|    if (id == 63) table[0][i / 64] = suf[i];
                                ^159k
  ------------------
  |  Branch (42:9): [True: 1.56%, False: 98.44%]
  ------------------
   43|  10.2M|  }
   44|  10.2M|  for (int min, i = n - 2; i >= 0; --i) {
                                                 ^10.2M
  ------------------
  |  Branch (44:28): [True: 100.00%, False: 0.00%]
  ------------------
   45|  10.2M|    int id = ~i & 63;
   46|  10.2M|    int value = pre[i];
   47|  10.2M|    pre[i] = min = id ? std::min(min, value) : value;
                                      ^10.0M                 ^159k
  ------------------
  |  Branch (47:20): [True: 98.44%, False: 1.56%]
  ------------------
   48|  10.2M|  }
   49|    307|  for (int i = 1; i < len; ++i) {
                                         ^282
  ------------------
  |  Branch (49:19): [True: 91.86%, False: 8.14%]
  ------------------
   50|  1.82M|    for (int j = 0, k = 1 << (i - 1); k < m; ++j, ++k) {
                                                           ^1.82M
  ------------------
  |  Branch (50:39): [True: 99.98%, False: 0.02%]
  ------------------
   51|  1.82M|      table[i][j] = std::min(table[i - 1][j], table[i - 1][k]);
   52|  1.82M|    }
   53|    282|  }
   54|  9.66M|  while (q--) {
  ------------------
  |  Branch (54:10): [True: 100.00%, False: 0.00%]
  ------------------
   55|  9.66M|    int u = node2id[rd.uh()];
   56|  9.66M|    int v = node2id[rd.uh()];
   57|  9.66M|    int l = std::min(u, v) + 1;
   58|  9.66M|    int r = std::max(u, v);
   59|  9.66M|    int L = l / 64;
   60|  9.66M|    int R = r / 64;
   61|  9.66M|    int w;
   62|  9.66M|    if (L < R - 1) {
  ------------------
  |  Branch (62:9): [True: 99.94%, False: 0.06%]
  ------------------
   63|  9.65M|      int p = pre[l];
   64|  9.65M|      int s = suf[r];
   65|  9.65M|      w = std::min(p, s);
   66|  9.65M|      int k = log(R - L - 1);
   67|  9.65M|      int a = table[k][L + 1];
   68|  9.65M|      int b = table[k][R - (1 << k)];
   69|  9.65M|      int tmp = std::min(a, b);
   70|  9.65M|      w = std::min(w, tmp);
   71|  9.65M|    } else if (L == R - 1) {
                         ^5.83k^5.83k
  ------------------
  |  Branch (71:16): [True: 66.83%, False: 33.17%]
  ------------------
   72|  3.90k|      int p = pre[l];
   73|  3.90k|      int s = suf[r];
   74|  3.90k|      w = std::min(p, s);
   75|  3.90k|    } else {
   76|  1.93k|      w = id2node[l];
   77|  40.3k|      for (int i = l + 1; i <= r; ++i) w = std::min(w, id2node[i]);
                                                ^38.3k^38.3k
  ------------------
  |  Branch (77:27): [True: 95.20%, False: 4.80%]
  ------------------
   78|  1.93k|    }
   79|  9.66M|    wt.uw(w);
   80|  9.66M|  }
   81|     25|  return 0;
   82|     25|}