/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| 20|def build_step_1(int u, int d, int p) -> void {
23| 20| size[u] = 1;
24| 20| depth[u] = d;
25| 20| parent[u] = p;
26| 58| for (int e = head[u]; e; e = edge[e].nxt) {
^38
------------------
| Branch (26:25): [True: 65.52%, False: 34.48%]
------------------
27| 38| if (int v = edge[e].to; v != p) {
------------------
| Branch (27:29): [True: 50.00%, False: 50.00%]
------------------
28| 19| build_step_1(v, d + 1, u);
29| 19| size[u] += size[v];
30| 19| if (heavy[u] == 0 || size[v] > size[heavy[u]]) {
^10
------------------
| Branch (30:11): [True: 47.37%, False: 52.63%]
| Branch (30:28): [True: 40.00%, False: 60.00%]
------------------
31| 13| heavy[u] = v;
32| 13| }
33| 19| }
34| 38| }
35| 20|}
36| |
37| 20|def build_step_2(int u, int a, int p) -> void {
38| 20| node2id[u] = id;
39| 20| id2node[id] = u;
40| 20| ++id;
41| 20| ances[u] = a;
42| 20| if (heavy[u]) build_step_2(heavy[u], a, u);
^9
------------------
| Branch (42:7): [True: 45.00%, False: 55.00%]
------------------
43| 58| for (int e = head[u]; e; e = edge[e].nxt) {
^38
------------------
| Branch (43:25): [True: 65.52%, False: 34.48%]
------------------
44| 38| if (int v = edge[e].to; v != heavy[u] && v != p) {
^29
------------------
| Branch (44:29): [True: 76.32%, False: 23.68%]
| Branch (44:46): [True: 34.48%, False: 65.52%]
------------------
45| 10| build_step_2(v, v, u);
46| 10| }
47| 38| }
48| 20|}
49| |
50| 500k|def lca(int u, int v) -> int {
51| 500k| if (depth[u] < 32 && depth[v] < 32) {
------------------
| Branch (51:7): [True: 100.00%, False: 0.00%]
| Branch (51:24): [True: 100.00%, False: 0.00%]
------------------
52| 890k| while (depth[u] > depth[v]) {
------------------
| Branch (52:12): [True: 43.83%, False: 56.17%]
------------------
53| 390k| u = parent[u];
54| 390k| }
55| 888k| while (depth[v] > depth[u]) {
------------------
| Branch (55:12): [True: 43.70%, False: 56.30%]
------------------
56| 388k| v = parent[v];
57| 388k| }
58| 997k| while (u != v) {
------------------
| Branch (58:12): [True: 49.86%, False: 50.14%]
------------------
59| 497k| u = parent[u];
60| 497k| v = parent[v];
61| 497k| }
62| 500k| return u;
63| 500k| }
64| 0| while (ances[u] != ances[v]) {
------------------
| Branch (64:10): [True: 0.00%, False: 0.00%]
------------------
65| 0| if (depth[ances[u]] > depth[ances[v]]) {
------------------
| Branch (65:9): [True: 0.00%, False: 0.00%]
------------------
66| 0| u = parent[ances[u]];
67| 0| } else {
68| 0| v = parent[ances[v]];
69| 0| }
70| 0| }
71| 0| return depth[u] < depth[v] ? u : v;
------------------
| Branch (71:10): [True: 0.00%, False: 0.00%]
------------------
72| 500k|}
73| |
74| 113k|def jump(int u, int d) -> int {
75| 113k| if (int t = depth[u] - d; t < 32) {
------------------
| Branch (75:29): [True: 100.00%, False: 0.00%]
------------------
76| 238k| while (t--) u = parent[u];
^124k
------------------
| Branch (76:12): [True: 52.21%, False: 47.79%]
------------------
77| 113k| return u;
78| 113k| }
79| 0| while (depth[ances[u]] > d) {
------------------
| Branch (79:10): [True: 0.00%, False: 0.00%]
------------------
80| 0| u = parent[ances[u]];
81| 0| }
82| 0| return id2node[node2id[u] - depth[u] + d];
83| 113k|}
84| |
85| |} // namespace
86| |
87| 1|int main() {
88| 1| rd rd;
89| 1| wt wt;
90| 1| int n = rd.uh();
91| 1| int q = rd.uh();
92| 1|#ifdef LOCAL
93| 1| id = 0;
94| 1| std::memset(head, 0, 4 * n);
95| 1| std::memset(heavy, 0, 4 * n);
96| 1| std::memset(parent, 0, 4 * n);
97| 1|#endif
98| 20| for (int i = 1; i < n; ++i) {
^19
------------------
| Branch (98:19): [True: 95.00%, False: 5.00%]
------------------
99| 19| int a = rd.uh();
100| 19| int b = rd.uh();
101| 19| edge[i * 2 | 0] = {b, head[a]}, head[a] = i * 2 | 0;
102| 19| edge[i * 2 | 1] = {a, head[b]}, head[b] = i * 2 | 1;
103| 19| }
104| 1| build_step_1(0, 0, -1);
105| 1| build_step_2(0, 0, -1);
106| 500k| while (q--) {
------------------
| Branch (106:10): [True: 100.00%, False: 0.00%]
------------------
107| 500k| int u = rd.uh();
108| 500k| int v = rd.uh();
109| 500k| int k = rd.uh();
110| 500k| int w = lca(u, v);
111| 500k| int du = depth[u];
112| 500k| int dv = depth[v];
113| 500k| int dw = depth[w];
114| 500k| if (k <= du - dw) {
------------------
| Branch (114:9): [True: 13.87%, False: 86.13%]
------------------
115| 69.3k| int x = jump(u, du - k);
116| 69.3k| wt.uw(x);
117| 430k| } else if (k <= du + dv - dw - dw) {
------------------
| Branch (117:16): [True: 10.36%, False: 89.64%]
------------------
118| 44.6k| int x = jump(v, dw + dw - du + k);
119| 44.6k| wt.uw(x);
120| 386k| } else {
121| 386k| wt.puts(" -1", 3);
122| 386k| }
123| 500k| }
124| 1| return 0;
125| 1|}