/tmp/solutions/build/tree_diameter-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 len;
11| | int nxt;
12| |} edge[N * 2];
13| |int pa[N];
14| |int head[N];
15| |
16| 926k|def tree_diameter(int u, int p) -> std::pair<u64, int> {
17| 926k| pa[u] = p;
18| 926k| std::pair<u64, int> ans{0, u};
19| 2.77M| for (int e = head[u]; e; e = edge[e].nxt) {
^1.85M
------------------
| Branch (19:25): [True: 66.67%, False: 33.33%]
------------------
20| 1.85M| int v = edge[e].to;
21| 1.85M| int len = edge[e].len;
22| 1.85M| if (v != p) {
------------------
| Branch (22:9): [True: 50.00%, False: 50.00%]
------------------
23| 926k| def res = tree_diameter(v, u);
24| 926k| res.first += len;
25| 926k| ans = std::max(ans, res);
26| 926k| }
27| 1.85M| }
28| 926k| return ans;
29| 926k|}
30| |
31| |} // namespace
32| |
33| 1|int main() {
34| 1| rd rd;
35| 1| wt wt;
36| 1| int n = rd.uh();
37| 1|#ifdef LOCAL
38| 1| std::memset(head, 0, 4 * n);
39| 1|#endif
40| 463k| for (int i = 1; i < n; ++i) {
^463k
------------------
| Branch (40:19): [True: 100.00%, False: 0.00%]
------------------
41| 463k| int a = rd.uh();
42| 463k| int b = rd.uh();
43| 463k| int c = rd.uw();
44| 463k| edge[i * 2 | 0] = {b, c, head[a]}, head[a] = i * 2 | 0;
45| 463k| edge[i * 2 | 1] = {a, c, head[b]}, head[b] = i * 2 | 1;
46| 463k| }
47| 1| let[_, u] = tree_diameter(0, -1);
48| 1| let[d, v] = tree_diameter(u, -1);
49| 1| int c = 0;
50| 58| for (int i = v; i != -1; i = pa[i]) ++c;
^57 ^57
------------------
| Branch (50:19): [True: 98.28%, False: 1.72%]
------------------
51| 1| wt.ud(d);
52| 1| wt.uw(c);
53| 58| for (int i = v; i != -1; i = pa[i]) wt.uw(i);
^57 ^57
------------------
| Branch (53:19): [True: 98.28%, False: 1.72%]
------------------
54| 1| return 0;
55| 1|}