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