/tmp/solutions/build/lca-slow.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|      5|def build_step_1(int u, int d) -> void {
   17|      5|  size[u] = 1;
   18|      5|  depth[u] = d;
   19|      9|  for (int v = head[u]; v; v = next[v]) {
                                         ^4
  ------------------
  |  Branch (19:25): [True: 44.44%, False: 55.56%]
  ------------------
   20|      4|    build_step_1(v, d + 1);
   21|      4|    size[u] += size[v];
   22|      4|    if (heavy[u] == 0 || size[v] > size[heavy[u]]) {
                                       ^2
  ------------------
  |  Branch (22:9): [True: 50.00%, False: 50.00%]
  |  Branch (22:26): [True: 0.00%, False: 100.00%]
  ------------------
   23|      2|      heavy[u] = v;
   24|      2|    }
   25|      4|  }
   26|      5|}
   27|       |
   28|      5|def build_step_2(int u, int a) -> void {
   29|      5|  ances[u] = a;
   30|      9|  for (int v = head[u]; v; v = next[v]) {
                                         ^4
  ------------------
  |  Branch (30:25): [True: 44.44%, False: 55.56%]
  ------------------
   31|      4|    if (v != heavy[u]) {
  ------------------
  |  Branch (31:9): [True: 50.00%, False: 50.00%]
  ------------------
   32|      2|      build_step_2(v, v);
   33|      2|    }
   34|      4|  }
   35|      5|  if (heavy[u]) build_step_2(heavy[u], a);
                              ^2
  ------------------
  |  Branch (35:7): [True: 40.00%, False: 60.00%]
  ------------------
   36|      5|}
   37|       |
   38|      5|def lca(int u, int v) -> int {
   39|      9|  while (ances[u] != ances[v]) {
  ------------------
  |  Branch (39:10): [True: 44.44%, False: 55.56%]
  ------------------
   40|      4|    if (depth[ances[u]] > depth[ances[v]]) {
  ------------------
  |  Branch (40:9): [True: 50.00%, False: 50.00%]
  ------------------
   41|      2|      u = parent[ances[u]];
   42|      2|    } else {
   43|      2|      v = parent[ances[v]];
   44|      2|    }
   45|      4|  }
   46|      5|  return depth[u] < depth[v] ? u : v;
                                             ^3  ^2
  ------------------
  |  Branch (46:10): [True: 60.00%, False: 40.00%]
  ------------------
   47|      5|}
   48|       |
   49|       |} // namespace
   50|       |
   51|      1|int main() {
   52|      1|  rd rd;
   53|      1|  wt wt;
   54|      1|  int n = rd.uh();
   55|      1|  int q = rd.uh();
   56|      1|#ifdef LOCAL
   57|      1|  std::memset(head, 0, 4 * n);
   58|      1|  std::memset(heavy, 0, 4 * n);
   59|      1|  std::memset(parent, 0, 4 * n);
   60|      1|#endif
   61|      5|  for (int i = 1; i < n; ++i) {
                                       ^4
  ------------------
  |  Branch (61:19): [True: 80.00%, False: 20.00%]
  ------------------
   62|      4|    int p = rd.uh();
   63|      4|    parent[i] = p;
   64|      4|    next[i] = head[p];
   65|      4|    head[p] = i;
   66|      4|  }
   67|      1|  build_step_1(0, 0);
   68|      1|  build_step_2(0, 0);
   69|      6|  while (q--) {
  ------------------
  |  Branch (69:10): [True: 83.33%, False: 16.67%]
  ------------------
   70|      5|    int u = rd.uh();
   71|      5|    int v = rd.uh();
   72|      5|    int w = lca(u, v);
   73|      5|    wt.uw(w);
   74|      5|  }
   75|      1|  return 0;
   76|      1|}