/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| 463k|def build_step_1(int u, int d) -> void {
17| 463k| size[u] = 1;
18| 463k| depth[u] = d;
19| 926k| for (int v = head[u]; v; v = next[v]) {
^463k
------------------
| Branch (19:25): [True: 50.00%, False: 50.00%]
------------------
20| 463k| build_step_1(v, d + 1);
21| 463k| size[u] += size[v];
22| 463k| if (heavy[u] == 0 || size[v] > size[heavy[u]]) {
^231k
------------------
| Branch (22:9): [True: 50.03%, False: 49.97%]
| Branch (22:26): [True: 46.81%, False: 53.19%]
------------------
23| 339k| heavy[u] = v;
24| 339k| }
25| 463k| }
26| 463k|}
27| |
28| 463k|def build_step_2(int u, int a) -> void {
29| 463k| ances[u] = a;
30| 926k| for (int v = head[u]; v; v = next[v]) {
^463k
------------------
| Branch (30:25): [True: 50.00%, False: 50.00%]
------------------
31| 463k| if (v != heavy[u]) {
------------------
| Branch (31:9): [True: 49.97%, False: 50.03%]
------------------
32| 231k| build_step_2(v, v);
33| 231k| }
34| 463k| }
35| 463k| if (heavy[u]) build_step_2(heavy[u], a);
^231k
------------------
| Branch (35:7): [True: 50.03%, False: 49.97%]
------------------
36| 463k|}
37| |
38| 412k|def lca(int u, int v) -> int {
39| 412k| if (depth[u] < 32 && depth[v] < 32) {
^412k
------------------
| Branch (39:7): [True: 100.00%, False: 0.00%]
| Branch (39:24): [True: 100.00%, False: 0.00%]
------------------
40| 1.00M| while (depth[u] > depth[v]) {
------------------
| Branch (40:12): [True: 58.87%, False: 41.13%]
------------------
41| 590k| u = parent[u];
42| 590k| }
43| 1.41M| while (depth[v] > depth[u]) {
------------------
| Branch (43:12): [True: 70.79%, False: 29.21%]
------------------
44| 1.00M| v = parent[v];
45| 1.00M| }
46| 4.36M| while (u != v) {
------------------
| Branch (46:12): [True: 90.54%, False: 9.46%]
------------------
47| 3.94M| u = parent[u];
48| 3.94M| v = parent[v];
49| 3.94M| }
50| 412k| return u;
51| 412k| }
52| 122| while (ances[u] != ances[v]) {
^15
------------------
| Branch (52:10): [True: 87.70%, False: 12.30%]
------------------
53| 107| if (depth[ances[u]] > depth[ances[v]]) {
------------------
| Branch (53:9): [True: 57.01%, False: 42.99%]
------------------
54| 61| u = parent[ances[u]];
55| 61| } else {
56| 46| v = parent[ances[v]];
57| 46| }
58| 107| }
59| 15| return depth[u] < depth[v] ? u : v;
^6 ^9
------------------
| Branch (59:10): [True: 40.00%, False: 60.00%]
------------------
60| 412k|}
61| |
62| |} // namespace
63| |
64| 1|int main() {
65| 1| rd rd;
66| 1| wt wt;
67| 1| int n = rd.uh();
68| 1| int q = rd.uh();
69| 1|#ifdef LOCAL
70| 1| std::memset(head, 0, 4 * n);
71| 1| std::memset(heavy, 0, 4 * n);
72| 1| std::memset(parent, 0, 4 * n);
73| 1|#endif
74| 463k| for (int i = 1; i < n; ++i) {
^463k
------------------
| Branch (74:19): [True: 100.00%, False: 0.00%]
------------------
75| 463k| int p = rd.uh();
76| 463k| parent[i] = p;
77| 463k| next[i] = head[p];
78| 463k| head[p] = i;
79| 463k| }
80| 1| build_step_1(0, 0);
81| 1| build_step_2(0, 0);
82| 412k| while (q--) {
------------------
| Branch (82:10): [True: 100.00%, False: 0.00%]
------------------
83| 412k| int u = rd.uh();
84| 412k| int v = rd.uh();
85| 412k| int w = lca(u, v);
86| 412k| wt.uw(w);
87| 412k| }
88| 1| return 0;
89| 1|}