/tmp/solutions/build/jump_on_tree-main.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|  6.61M|def build_step_1(int u, int d, int p) -> void {
   23|  6.61M|  size[u] = 1;
   24|  6.61M|  depth[u] = d;
   25|  6.61M|  parent[u] = p;
   26|  19.8M|  for (int e = head[u]; e; e = edge[e].nxt) {
                                         ^13.2M
  ------------------
  |  Branch (26:25): [True: 66.67%, False: 33.33%]
  ------------------
   27|  13.2M|    if (int v = edge[e].to; v != p) {
  ------------------
  |  Branch (27:29): [True: 50.00%, False: 50.00%]
  ------------------
   28|  6.61M|      build_step_1(v, d + 1, u);
   29|  6.61M|      size[u] += size[v];
   30|  6.61M|      if (heavy[u] == 0 || size[v] > size[heavy[u]]) {
                                         ^3.46M
  ------------------
  |  Branch (30:11): [True: 47.67%, False: 52.33%]
  |  Branch (30:28): [True: 19.68%, False: 80.32%]
  ------------------
   31|  3.83M|        heavy[u] = v;
   32|  3.83M|      }
   33|  6.61M|    }
   34|  13.2M|  }
   35|  6.61M|}
   36|       |
   37|  6.61M|def build_step_2(int u, int a, int p) -> void {
   38|  6.61M|  node2id[u] = id;
   39|  6.61M|  id2node[id] = u;
   40|  6.61M|  ++id;
   41|  6.61M|  ances[u] = a;
   42|  6.61M|  if (heavy[u]) build_step_2(heavy[u], a, u);
                              ^3.15M
  ------------------
  |  Branch (42:7): [True: 47.67%, False: 52.33%]
  ------------------
   43|  19.8M|  for (int e = head[u]; e; e = edge[e].nxt) {
                                         ^13.2M
  ------------------
  |  Branch (43:25): [True: 66.67%, False: 33.33%]
  ------------------
   44|  13.2M|    if (int v = edge[e].to; v != heavy[u] && v != p) {
                                                           ^8.76M
  ------------------
  |  Branch (44:29): [True: 66.26%, False: 33.74%]
  |  Branch (44:46): [True: 39.49%, False: 60.51%]
  ------------------
   45|  3.46M|      build_step_2(v, v, u);
   46|  3.46M|    }
   47|  13.2M|  }
   48|  6.61M|}
   49|       |
   50|  10.0M|def lca(int u, int v) -> int {
   51|  10.0M|  if (depth[u] < 32 && depth[v] < 32) {
                                     ^7.50M
  ------------------
  |  Branch (51:7): [True: 75.00%, False: 25.00%]
  |  Branch (51:24): [True: 99.99%, False: 0.01%]
  ------------------
   52|  16.2M|    while (depth[u] > depth[v]) {
  ------------------
  |  Branch (52:12): [True: 53.87%, False: 46.13%]
  ------------------
   53|  8.75M|      u = parent[u];
   54|  8.75M|    }
   55|  16.2M|    while (depth[v] > depth[u]) {
  ------------------
  |  Branch (55:12): [True: 53.84%, False: 46.16%]
  ------------------
   56|  8.74M|      v = parent[v];
   57|  8.74M|    }
   58|  45.8M|    while (u != v) {
  ------------------
  |  Branch (58:12): [True: 83.65%, False: 16.35%]
  ------------------
   59|  38.3M|      u = parent[u];
   60|  38.3M|      v = parent[v];
   61|  38.3M|    }
   62|  7.49M|    return u;
   63|  7.49M|  }
   64|  5.46M|  while (ances[u] != ances[v]) {
                ^2.50M
  ------------------
  |  Branch (64:10): [True: 54.25%, False: 45.75%]
  ------------------
   65|  2.96M|    if (depth[ances[u]] > depth[ances[v]]) {
  ------------------
  |  Branch (65:9): [True: 50.01%, False: 49.99%]
  ------------------
   66|  1.48M|      u = parent[ances[u]];
   67|  1.48M|    } else {
   68|  1.48M|      v = parent[ances[v]];
   69|  1.48M|    }
   70|  2.96M|  }
   71|  2.50M|  return depth[u] < depth[v] ? u : v;
                                             ^1.24M^1.25M
  ------------------
  |  Branch (71:10): [True: 49.95%, False: 50.05%]
  ------------------
   72|  10.0M|}
   73|       |
   74|  7.10M|def jump(int u, int d) -> int {
   75|  7.10M|  if (int t = depth[u] - d; t < 32) {
  ------------------
  |  Branch (75:29): [True: 67.71%, False: 32.29%]
  ------------------
   76|  23.4M|    while (t--) u = parent[u];
                              ^18.5M
  ------------------
  |  Branch (76:12): [True: 79.43%, False: 20.57%]
  ------------------
   77|  4.81M|    return u;
   78|  4.81M|  }
   79|  3.26M|  while (depth[ances[u]] > d) {
                ^2.29M
  ------------------
  |  Branch (79:10): [True: 29.68%, False: 70.32%]
  ------------------
   80|   969k|    u = parent[ances[u]];
   81|   969k|  }
   82|  2.29M|  return id2node[node2id[u] - depth[u] + d];
   83|  7.10M|}
   84|       |
   85|       |} // namespace
   86|       |
   87|     21|int main() {
   88|     21|  rd rd;
   89|     21|  wt wt;
   90|     21|  int n = rd.uh();
   91|     21|  int q = rd.uh();
   92|     21|#ifdef LOCAL
   93|     21|  id = 0;
   94|     21|  std::memset(head, 0, 4 * n);
   95|     21|  std::memset(heavy, 0, 4 * n);
   96|     21|  std::memset(parent, 0, 4 * n);
   97|     21|#endif
   98|  6.61M|  for (int i = 1; i < n; ++i) {
                                       ^6.61M
  ------------------
  |  Branch (98:19): [True: 100.00%, False: 0.00%]
  ------------------
   99|  6.61M|    int a = rd.uh();
  100|  6.61M|    int b = rd.uh();
  101|  6.61M|    edge[i * 2 | 0] = {b, head[a]}, head[a] = i * 2 | 0;
  102|  6.61M|    edge[i * 2 | 1] = {a, head[b]}, head[b] = i * 2 | 1;
  103|  6.61M|  }
  104|     21|  build_step_1(0, 0, -1);
  105|     21|  build_step_2(0, 0, -1);
  106|  10.0M|  while (q--) {
  ------------------
  |  Branch (106:10): [True: 100.00%, False: 0.00%]
  ------------------
  107|  10.0M|    int u = rd.uh();
  108|  10.0M|    int v = rd.uh();
  109|  10.0M|    int k = rd.uh();
  110|  10.0M|    int w = lca(u, v);
  111|  10.0M|    int du = depth[u];
  112|  10.0M|    int dv = depth[v];
  113|  10.0M|    int dw = depth[w];
  114|  10.0M|    if (k <= du - dw) {
  ------------------
  |  Branch (114:9): [True: 38.72%, False: 61.28%]
  ------------------
  115|  3.87M|      int x = jump(u, du - k);
  116|  3.87M|      wt.uw(x);
  117|  6.12M|    } else if (k <= du + dv - dw - dw) {
  ------------------
  |  Branch (117:16): [True: 52.82%, False: 47.18%]
  ------------------
  118|  3.23M|      int x = jump(v, dw + dw - du + k);
  119|  3.23M|      wt.uw(x);
  120|  3.23M|    } else {
  121|  2.89M|      wt.puts(" -1", 3);
  122|  2.89M|    }
  123|  10.0M|  }
  124|     21|  return 0;
  125|     21|}