/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|  53.3k|  for (int i = 1; i < n; ++i) parent[i] = rd.uh();
                                       ^53.3k^53.3k
  ------------------
  |  Branch (23:19): [True: 100.00%, False: 0.00%]
  ------------------
   24|  53.3k|  for (int i = n - 1; i > 0; --i) node2id[parent[i]] += node2id[i] + 1;
                                           ^53.3k^53.3k
  ------------------
  |  Branch (24:23): [True: 100.00%, False: 0.00%]
  ------------------
   25|  53.3k|  for (int i = 1; i < n; ++i) {
                                       ^53.3k
  ------------------
  |  Branch (25:19): [True: 100.00%, False: 0.00%]
  ------------------
   26|  53.3k|    int p = parent[i];
   27|  53.3k|    int &u = node2id[i];
   28|  53.3k|    int &w = node2id[p];
   29|  53.3k|    int t = w - u - 1;
   30|  53.3k|    u = w, w = t;
   31|  53.3k|  }
   32|  53.3k|  for (int i = 1; i < n; ++i) id2node[node2id[i]] = parent[i];
                                       ^53.3k^53.3k
  ------------------
  |  Branch (32:19): [True: 100.00%, False: 0.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|  53.3k|  for (int min, i = 0; i < n; ++i) {
                                            ^53.3k
  ------------------
  |  Branch (38:24): [True: 100.00%, False: 0.00%]
  ------------------
   39|  53.3k|    int id = i & 63;
   40|  53.3k|    int value = pre[i] = id2node[i];
   41|  53.3k|    suf[i] = min = id ? std::min(min, value) : value;
                                      ^52.5k                 ^834
  ------------------
  |  Branch (41:20): [True: 98.44%, False: 1.56%]
  ------------------
   42|  53.3k|    if (id == 63) table[0][i / 64] = suf[i];
                                ^833
  ------------------
  |  Branch (42:9): [True: 1.56%, False: 98.44%]
  ------------------
   43|  53.3k|  }
   44|  53.3k|  for (int min, i = n - 2; i >= 0; --i) {
                                                 ^53.3k
  ------------------
  |  Branch (44:28): [True: 100.00%, False: 0.00%]
  ------------------
   45|  53.3k|    int id = ~i & 63;
   46|  53.3k|    int value = pre[i];
   47|  53.3k|    pre[i] = min = id ? std::min(min, value) : value;
                                      ^52.5k                 ^833
  ------------------
  |  Branch (47:20): [True: 98.44%, False: 1.56%]
  ------------------
   48|  53.3k|  }
   49|     10|  for (int i = 1; i < len; ++i) {
                                         ^9
  ------------------
  |  Branch (49:19): [True: 90.00%, False: 10.00%]
  ------------------
   50|  7.00k|    for (int j = 0, k = 1 << (i - 1); k < m; ++j, ++k) {
                                                           ^6.99k
  ------------------
  |  Branch (50:39): [True: 99.87%, False: 0.13%]
  ------------------
   51|  6.99k|      table[i][j] = std::min(table[i - 1][j], table[i - 1][k]);
   52|  6.99k|    }
   53|      9|  }
   54|   382k|  while (q--) {
  ------------------
  |  Branch (54:10): [True: 100.00%, False: 0.00%]
  ------------------
   55|   382k|    int u = node2id[rd.uh()];
   56|   382k|    int v = node2id[rd.uh()];
   57|   382k|    int l = std::min(u, v) + 1;
   58|   382k|    int r = std::max(u, v);
   59|   382k|    int L = l / 64;
   60|   382k|    int R = r / 64;
   61|   382k|    int w;
   62|   382k|    if (L < R - 1) {
  ------------------
  |  Branch (62:9): [True: 99.64%, False: 0.36%]
  ------------------
   63|   380k|      int p = pre[l];
   64|   380k|      int s = suf[r];
   65|   380k|      w = std::min(p, s);
   66|   380k|      int k = log(R - L - 1);
   67|   380k|      int a = table[k][L + 1];
   68|   380k|      int b = table[k][R - (1 << k)];
   69|   380k|      int tmp = std::min(a, b);
   70|   380k|      w = std::min(w, tmp);
   71|   380k|    } else if (L == R - 1) {
                         ^1.38k^1.38k
  ------------------
  |  Branch (71:16): [True: 66.33%, False: 33.67%]
  ------------------
   72|    920|      int p = pre[l];
   73|    920|      int s = suf[r];
   74|    920|      w = std::min(p, s);
   75|    920|    } else {
   76|    467|      w = id2node[l];
   77|  9.56k|      for (int i = l + 1; i <= r; ++i) w = std::min(w, id2node[i]);
                                                ^9.09k^9.09k
  ------------------
  |  Branch (77:27): [True: 95.12%, False: 4.88%]
  ------------------
   78|    467|    }
   79|   382k|    wt.uw(w);
   80|   382k|  }
   81|      1|  return 0;
   82|      1|}