/tmp/solutions/build/tree_diameter-fast.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| |std::pair<u64, int> queue[N];
16| |
17| |} // namespace
18| |
19| 1|int main() {
20| 1| rd rd;
21| 1| wt wt;
22| 1| int n = rd.uh();
23| 1|#ifdef LOCAL
24| 1| std::memset(head, 0, 4 * n);
25| 1|#endif
26| 500k| for (int i = 1; i < n; ++i) {
^499k
------------------
| Branch (26:19): [True: 100.00%, False: 0.00%]
------------------
27| 499k| int a = rd.uh();
28| 499k| int b = rd.uh();
29| 499k| int c = rd.uw();
30| 499k| edge[i * 2 | 0] = {b, c, head[a]}, head[a] = i * 2 | 0;
31| 499k| edge[i * 2 | 1] = {a, c, head[b]}, head[b] = i * 2 | 1;
32| 499k| }
33| 1| std::pair<u64, int> ans;
34| 2| let bfs = [&](int u) {
^1
35| 2| pa[u] = -1;
36| 2| queue[0] = {0, u};
37| 2| ans = {};
38| 1.00M| for (int i = 0, j = 0; i < n; ++i) {
^1.00M
------------------
| Branch (38:28): [True: 100.00%, False: 0.00%]
------------------
39| 1.00M| let[d, u] = queue[i];
40| 2.99M| for (int e = head[u]; e; e = edge[e].nxt) {
^1.99M
------------------
| Branch (40:29): [True: 66.67%, False: 33.33%]
------------------
41| 1.99M| int v = edge[e].to;
42| 1.99M| int len = edge[e].len;
43| 1.99M| if (v != pa[u]) {
------------------
| Branch (43:13): [True: 50.00%, False: 50.00%]
------------------
44| 999k| pa[v] = u;
45| 999k| ans = std::max(ans, queue[++j] = {d + len, v});
46| 999k| }
47| 1.99M| }
48| 1.00M| }
49| 2| };
50| 1| bfs(0);
51| 1| int u = ans.second;
52| 1| bfs(u);
53| 1| int v = ans.second;
54| 1| u64 d = ans.first;
55| 1| wt.ud(d);
56| 1| int c = 0;
57| 51| for (int i = v; i != -1; i = pa[i]) ++c;
^50 ^50
------------------
| Branch (57:19): [True: 98.04%, False: 1.96%]
------------------
58| 1| wt.uw(c);
59| 51| for (int i = v; i != -1; i = pa[i]) wt.uw(i);
^50 ^50
------------------
| Branch (59:19): [True: 98.04%, False: 1.96%]
------------------
60| 1| return 0;
61| 1|}