/tmp/solutions/build/jump_on_tree-slow.cpp:
    1|       |#include <common.h>
    2|       |prelude;
    3|       |
    4|       |namespace {
    5|       |
    6|       |constexpr int N = 5e5;
    7|       |
    8|       |struct {
    9|       |  int to;
   10|       |  int nxt;
   11|       |} edge[N * 2];
   12|       |int head[N];
   13|       |int size[N];
   14|       |int depth[N];
   15|       |int heavy[N];
   16|       |int ances[N];
   17|       |int parent[N];
   18|       |int node2id[N];
   19|       |int id2node[N];
   20|       |int id;
   21|       |
   22|     70|def build_step_1(int u, int d, int p) -> void {
   23|     70|  size[u] = 1;
   24|     70|  depth[u] = d;
   25|     70|  parent[u] = p;
   26|    208|  for (int e = head[u]; e; e = edge[e].nxt) {
                                         ^138
  ------------------
  |  Branch (26:25): [True: 66.35%, False: 33.65%]
  ------------------
   27|    138|    if (int v = edge[e].to; v != p) {
  ------------------
  |  Branch (27:29): [True: 50.00%, False: 50.00%]
  ------------------
   28|     69|      build_step_1(v, d + 1, u);
   29|     69|      size[u] += size[v];
   30|     69|      if (heavy[u] == 0 || size[v] > size[heavy[u]]) {
                                         ^34
  ------------------
  |  Branch (30:11): [True: 50.72%, False: 49.28%]
  |  Branch (30:28): [True: 32.35%, False: 67.65%]
  ------------------
   31|     46|        heavy[u] = v;
   32|     46|      }
   33|     69|    }
   34|    138|  }
   35|     70|}
   36|       |
   37|     70|def build_step_2(int u, int a, int p) -> void {
   38|     70|  node2id[u] = id;
   39|     70|  id2node[id] = u;
   40|     70|  ++id;
   41|     70|  ances[u] = a;
   42|     70|  if (heavy[u]) build_step_2(heavy[u], a, u);
                              ^35
  ------------------
  |  Branch (42:7): [True: 50.00%, False: 50.00%]
  ------------------
   43|    208|  for (int e = head[u]; e; e = edge[e].nxt) {
                                         ^138
  ------------------
  |  Branch (43:25): [True: 66.35%, False: 33.65%]
  ------------------
   44|    138|    if (int v = edge[e].to; v != heavy[u] && v != p) {
                                                           ^103
  ------------------
  |  Branch (44:29): [True: 74.64%, False: 25.36%]
  |  Branch (44:46): [True: 33.01%, False: 66.99%]
  ------------------
   45|     34|      build_step_2(v, v, u);
   46|     34|    }
   47|    138|  }
   48|     70|}
   49|       |
   50|   500k|def lca(int u, int v) -> int {
   51|  1.64M|  while (ances[u] != ances[v]) {
  ------------------
  |  Branch (51:10): [True: 69.59%, False: 30.41%]
  ------------------
   52|  1.14M|    if (depth[ances[u]] > depth[ances[v]]) {
  ------------------
  |  Branch (52:9): [True: 50.03%, False: 49.97%]
  ------------------
   53|   572k|      u = parent[ances[u]];
   54|   572k|    } else {
   55|   571k|      v = parent[ances[v]];
   56|   571k|    }
   57|  1.14M|  }
   58|   500k|  return depth[u] < depth[v] ? u : v;
                                             ^185k^314k
  ------------------
  |  Branch (58:10): [True: 37.19%, False: 62.81%]
  ------------------
   59|   500k|}
   60|       |
   61|  43.0k|def jump(int u, int d) -> int {
   62|  63.3k|  while (depth[ances[u]] > d) {
  ------------------
  |  Branch (62:10): [True: 32.03%, False: 67.97%]
  ------------------
   63|  20.2k|    u = parent[ances[u]];
   64|  20.2k|  }
   65|  43.0k|  return id2node[node2id[u] - depth[u] + d];
   66|  43.0k|}
   67|       |
   68|       |} // namespace
   69|       |
   70|      1|int main() {
   71|      1|  rd rd;
   72|      1|  wt wt;
   73|      1|  int n = rd.uh();
   74|      1|  int q = rd.uh();
   75|      1|#ifdef LOCAL
   76|      1|  id = 0;
   77|      1|  std::memset(head, 0, 4 * n);
   78|      1|  std::memset(heavy, 0, 4 * n);
   79|      1|  std::memset(parent, 0, 4 * n);
   80|      1|#endif
   81|     70|  for (int i = 1; i < n; ++i) {
                                       ^69
  ------------------
  |  Branch (81:19): [True: 98.57%, False: 1.43%]
  ------------------
   82|     69|    int a = rd.uh();
   83|     69|    int b = rd.uh();
   84|     69|    edge[i * 2 | 0] = {b, head[a]}, head[a] = i * 2 | 0;
   85|     69|    edge[i * 2 | 1] = {a, head[b]}, head[b] = i * 2 | 1;
   86|     69|  }
   87|      1|  build_step_1(0, 0, -1);
   88|      1|  build_step_2(0, 0, -1);
   89|   500k|  while (q--) {
  ------------------
  |  Branch (89:10): [True: 100.00%, False: 0.00%]
  ------------------
   90|   500k|    int u = rd.uh();
   91|   500k|    int v = rd.uh();
   92|   500k|    int k = rd.uh();
   93|   500k|    int w = lca(u, v);
   94|   500k|    int du = depth[u];
   95|   500k|    int dv = depth[v];
   96|   500k|    int dw = depth[w];
   97|   500k|    if (k <= du - dw) {
  ------------------
  |  Branch (97:9): [True: 5.03%, False: 94.97%]
  ------------------
   98|  25.1k|      int x = jump(u, du - k);
   99|  25.1k|      wt.uw(x);
  100|   474k|    } else if (k <= du + dv - dw - dw) {
  ------------------
  |  Branch (100:16): [True: 3.77%, False: 96.23%]
  ------------------
  101|  17.9k|      int x = jump(v, dw + dw - du + k);
  102|  17.9k|      wt.uw(x);
  103|   456k|    } else {
  104|   456k|      wt.puts(" -1", 3);
  105|   456k|    }
  106|   500k|  }
  107|      1|  return 0;
  108|      1|}