/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| 10.2M|def build_step_1(int u, int d) -> void {
17| 10.2M| size[u] = 1;
18| 10.2M| depth[u] = d;
19| 20.4M| for (int v = head[u]; v; v = next[v]) {
^10.2M
------------------
| Branch (19:25): [True: 50.00%, False: 50.00%]
------------------
20| 10.2M| build_step_1(v, d + 1);
21| 10.2M| size[u] += size[v];
22| 10.2M| if (heavy[u] == 0 || size[v] > size[heavy[u]]) {
^2.68M
------------------
| Branch (22:9): [True: 73.78%, False: 26.22%]
| Branch (22:26): [True: 32.79%, False: 67.21%]
------------------
23| 8.42M| heavy[u] = v;
24| 8.42M| }
25| 10.2M| }
26| 10.2M|}
27| |
28| 10.2M|def build_step_2(int u, int a) -> void {
29| 10.2M| ances[u] = a;
30| 20.4M| for (int v = head[u]; v; v = next[v]) {
^10.2M
------------------
| Branch (30:25): [True: 50.00%, False: 50.00%]
------------------
31| 10.2M| if (v != heavy[u]) {
------------------
| Branch (31:9): [True: 26.22%, False: 73.78%]
------------------
32| 2.68M| build_step_2(v, v);
33| 2.68M| }
34| 10.2M| }
35| 10.2M| if (heavy[u]) build_step_2(heavy[u], a);
^7.54M
------------------
| Branch (35:7): [True: 73.78%, False: 26.22%]
------------------
36| 10.2M|}
37| |
38| 9.66M|def lca(int u, int v) -> int {
39| 60.6M| while (ances[u] != ances[v]) {
------------------
| Branch (39:10): [True: 84.06%, False: 15.94%]
------------------
40| 50.9M| if (depth[ances[u]] > depth[ances[v]]) {
------------------
| Branch (40:9): [True: 52.22%, False: 47.78%]
------------------
41| 26.6M| u = parent[ances[u]];
42| 26.6M| } else {
43| 24.3M| v = parent[ances[v]];
44| 24.3M| }
45| 50.9M| }
46| 9.66M| return depth[u] < depth[v] ? u : v;
^7.22M^2.43M
------------------
| Branch (46:10): [True: 74.75%, False: 25.25%]
------------------
47| 9.66M|}
48| |
49| |} // namespace
50| |
51| 25|int main() {
52| 25| rd rd;
53| 25| wt wt;
54| 25| int n = rd.uh();
55| 25| int q = rd.uh();
56| 25|#ifdef LOCAL
57| 25| std::memset(head, 0, 4 * n);
58| 25| std::memset(heavy, 0, 4 * n);
59| 25| std::memset(parent, 0, 4 * n);
60| 25|#endif
61| 10.2M| for (int i = 1; i < n; ++i) {
^10.2M
------------------
| Branch (61:19): [True: 100.00%, False: 0.00%]
------------------
62| 10.2M| int p = rd.uh();
63| 10.2M| parent[i] = p;
64| 10.2M| next[i] = head[p];
65| 10.2M| head[p] = i;
66| 10.2M| }
67| 25| build_step_1(0, 0);
68| 25| build_step_2(0, 0);
69| 9.66M| while (q--) {
------------------
| Branch (69:10): [True: 100.00%, False: 0.00%]
------------------
70| 9.66M| int u = rd.uh();
71| 9.66M| int v = rd.uh();
72| 9.66M| int w = lca(u, v);
73| 9.66M| wt.uw(w);
74| 9.66M| }
75| 25| return 0;
76| 25|}