/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|   500k|  for (int i = 1; i < n; ++i) parent[i] = rd.uh();
                                       ^499k^499k
  ------------------
  |  Branch (23:19): [True: 100.00%, False: 0.00%]
  ------------------
   24|   500k|  for (int i = n - 1; i > 0; --i) node2id[parent[i]] += node2id[i] + 1;
                                           ^499k^499k
  ------------------
  |  Branch (24:23): [True: 100.00%, False: 0.00%]
  ------------------
   25|   500k|  for (int i = 1; i < n; ++i) {
                                       ^499k
  ------------------
  |  Branch (25:19): [True: 100.00%, False: 0.00%]
  ------------------
   26|   499k|    int p = parent[i];
   27|   499k|    int &u = node2id[i];
   28|   499k|    int &w = node2id[p];
   29|   499k|    int t = w - u - 1;
   30|   499k|    u = w, w = t;
   31|   499k|  }
   32|   500k|  for (int i = 1; i < n; ++i) id2node[node2id[i]] = parent[i];
                                       ^499k^499k
  ------------------
  |  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|   500k|  for (int min, i = 0; i < n; ++i) {
                                            ^500k
  ------------------
  |  Branch (38:24): [True: 100.00%, False: 0.00%]
  ------------------
   39|   500k|    int id = i & 63;
   40|   500k|    int value = pre[i] = id2node[i];
   41|   500k|    suf[i] = min = id ? std::min(min, value) : value;
                                      ^492k                  ^7.81k
  ------------------
  |  Branch (41:20): [True: 98.44%, False: 1.56%]
  ------------------
   42|   500k|    if (id == 63) table[0][i / 64] = suf[i];
                                ^7.81k
  ------------------
  |  Branch (42:9): [True: 1.56%, False: 98.44%]
  ------------------
   43|   500k|  }
   44|   500k|  for (int min, i = n - 2; i >= 0; --i) {
                                                 ^499k
  ------------------
  |  Branch (44:28): [True: 100.00%, False: 0.00%]
  ------------------
   45|   499k|    int id = ~i & 63;
   46|   499k|    int value = pre[i];
   47|   499k|    pre[i] = min = id ? std::min(min, value) : value;
                                      ^492k                  ^7.81k
  ------------------
  |  Branch (47:20): [True: 98.44%, False: 1.56%]
  ------------------
   48|   499k|  }
   49|     13|  for (int i = 1; i < len; ++i) {
                                         ^12
  ------------------
  |  Branch (49:19): [True: 92.31%, False: 7.69%]
  ------------------
   50|  89.6k|    for (int j = 0, k = 1 << (i - 1); k < m; ++j, ++k) {
                                                           ^89.6k
  ------------------
  |  Branch (50:39): [True: 99.99%, False: 0.01%]
  ------------------
   51|  89.6k|      table[i][j] = std::min(table[i - 1][j], table[i - 1][k]);
   52|  89.6k|    }
   53|     12|  }
   54|   500k|  while (q--) {
  ------------------
  |  Branch (54:10): [True: 100.00%, False: 0.00%]
  ------------------
   55|   500k|    int u = node2id[rd.uh()];
   56|   500k|    int v = node2id[rd.uh()];
   57|   500k|    int l = std::min(u, v) + 1;
   58|   500k|    int r = std::max(u, v);
   59|   500k|    int L = l / 64;
   60|   500k|    int R = r / 64;
   61|   500k|    int w;
   62|   500k|    if (L < R - 1) {
  ------------------
  |  Branch (62:9): [True: 99.96%, False: 0.04%]
  ------------------
   63|   499k|      int p = pre[l];
   64|   499k|      int s = suf[r];
   65|   499k|      w = std::min(p, s);
   66|   499k|      int k = log(R - L - 1);
   67|   499k|      int a = table[k][L + 1];
   68|   499k|      int b = table[k][R - (1 << k)];
   69|   499k|      int tmp = std::min(a, b);
   70|   499k|      w = std::min(w, tmp);
   71|   499k|    } else if (L == R - 1) {
                         ^192^192
  ------------------
  |  Branch (71:16): [True: 70.83%, False: 29.17%]
  ------------------
   72|    136|      int p = pre[l];
   73|    136|      int s = suf[r];
   74|    136|      w = std::min(p, s);
   75|    136|    } else {
   76|     56|      w = id2node[l];
   77|  1.00k|      for (int i = l + 1; i <= r; ++i) w = std::min(w, id2node[i]);
                                                ^948 ^948
  ------------------
  |  Branch (77:27): [True: 94.42%, False: 5.58%]
  ------------------
   78|     56|    }
   79|   500k|    wt.uw(w);
   80|   500k|  }
   81|      1|  return 0;
   82|      1|}