/tmp/solutions/build/lca-main.cpp:
    1|       |#include <common.h>
    2|       |prelude;
    3|       |
    4|       |namespace {
    5|       |
    6|       |constexpr int N = 5e5;
    7|       |
    8|       |int next[N];
    9|       |int head[N];
   10|       |int size[N];
   11|       |int depth[N];
   12|       |int heavy[N];
   13|       |int ances[N];
   14|       |int parent[N];
   15|       |
   16|  10.2M|def build_step_1(int u, int d) -> void {
   17|  10.2M|  size[u] = 1;
   18|  10.2M|  depth[u] = d;
   19|  20.4M|  for (int v = head[u]; v; v = next[v]) {
                                         ^10.2M
  ------------------
  |  Branch (19:25): [True: 50.00%, False: 50.00%]
  ------------------
   20|  10.2M|    build_step_1(v, d + 1);
   21|  10.2M|    size[u] += size[v];
   22|  10.2M|    if (heavy[u] == 0 || size[v] > size[heavy[u]]) {
                                       ^2.68M
  ------------------
  |  Branch (22:9): [True: 73.78%, False: 26.22%]
  |  Branch (22:26): [True: 32.79%, False: 67.21%]
  ------------------
   23|  8.42M|      heavy[u] = v;
   24|  8.42M|    }
   25|  10.2M|  }
   26|  10.2M|}
   27|       |
   28|  10.2M|def build_step_2(int u, int a) -> void {
   29|  10.2M|  ances[u] = a;
   30|  20.4M|  for (int v = head[u]; v; v = next[v]) {
                                         ^10.2M
  ------------------
  |  Branch (30:25): [True: 50.00%, False: 50.00%]
  ------------------
   31|  10.2M|    if (v != heavy[u]) {
  ------------------
  |  Branch (31:9): [True: 26.22%, False: 73.78%]
  ------------------
   32|  2.68M|      build_step_2(v, v);
   33|  2.68M|    }
   34|  10.2M|  }
   35|  10.2M|  if (heavy[u]) build_step_2(heavy[u], a);
                              ^7.54M
  ------------------
  |  Branch (35:7): [True: 73.78%, False: 26.22%]
  ------------------
   36|  10.2M|}
   37|       |
   38|  9.66M|def lca(int u, int v) -> int {
   39|  9.66M|  if (depth[u] < 32 && depth[v] < 32) {
                                     ^4.33M
  ------------------
  |  Branch (39:7): [True: 44.84%, False: 55.16%]
  |  Branch (39:24): [True: 99.97%, False: 0.03%]
  ------------------
   40|  8.74M|    while (depth[u] > depth[v]) {
  ------------------
  |  Branch (40:12): [True: 50.48%, False: 49.52%]
  ------------------
   41|  4.41M|      u = parent[u];
   42|  4.41M|    }
   43|  12.4M|    while (depth[v] > depth[u]) {
  ------------------
  |  Branch (43:12): [True: 65.11%, False: 34.89%]
  ------------------
   44|  8.08M|      v = parent[v];
   45|  8.08M|    }
   46|  54.0M|    while (u != v) {
  ------------------
  |  Branch (46:12): [True: 91.99%, False: 8.01%]
  ------------------
   47|  49.7M|      u = parent[u];
   48|  49.7M|      v = parent[v];
   49|  49.7M|    }
   50|  4.33M|    return u;
   51|  4.33M|  }
   52|  7.89M|  while (ances[u] != ances[v]) {
                ^5.33M
  ------------------
  |  Branch (52:10): [True: 32.45%, False: 67.55%]
  ------------------
   53|  2.56M|    if (depth[ances[u]] > depth[ances[v]]) {
  ------------------
  |  Branch (53:9): [True: 79.28%, False: 20.72%]
  ------------------
   54|  2.03M|      u = parent[ances[u]];
   55|  2.03M|    } else {
   56|   530k|      v = parent[ances[v]];
   57|   530k|    }
   58|  2.56M|  }
   59|  5.33M|  return depth[u] < depth[v] ? u : v;
                                             ^5.33M^65
  ------------------
  |  Branch (59:10): [True: 100.00%, False: 0.00%]
  ------------------
   60|  9.66M|}
   61|       |
   62|       |} // namespace
   63|       |
   64|     25|int main() {
   65|     25|  rd rd;
   66|     25|  wt wt;
   67|     25|  int n = rd.uh();
   68|     25|  int q = rd.uh();
   69|     25|#ifdef LOCAL
   70|     25|  std::memset(head, 0, 4 * n);
   71|     25|  std::memset(heavy, 0, 4 * n);
   72|     25|  std::memset(parent, 0, 4 * n);
   73|     25|#endif
   74|  10.2M|  for (int i = 1; i < n; ++i) {
                                       ^10.2M
  ------------------
  |  Branch (74:19): [True: 100.00%, False: 0.00%]
  ------------------
   75|  10.2M|    int p = rd.uh();
   76|  10.2M|    parent[i] = p;
   77|  10.2M|    next[i] = head[p];
   78|  10.2M|    head[p] = i;
   79|  10.2M|  }
   80|     25|  build_step_1(0, 0);
   81|     25|  build_step_2(0, 0);
   82|  9.66M|  while (q--) {
  ------------------
  |  Branch (82:10): [True: 100.00%, False: 0.00%]
  ------------------
   83|  9.66M|    int u = rd.uh();
   84|  9.66M|    int v = rd.uh();
   85|  9.66M|    int w = lca(u, v);
   86|  9.66M|    wt.uw(w);
   87|  9.66M|  }
   88|     25|  return 0;
   89|     25|}