/tmp/solutions/build/tree_diameter-slow.cpp:
1| |#include <common.h>
2| |prelude;
3| |
4| |namespace {
5| |
6| |constexpr int N = 5e5;
7| |
8| |struct edge {
9| | int to;
10| | int len;
11| |};
12| |
13| |int pa[N];
14| |std::vector<edge> ch[N];
15| |
16| 1.00M|def tree_diameter(int u, int p) -> std::pair<u64, int> {
17| 1.00M| pa[u] = p;
18| 1.00M| std::pair<u64, int> ans{0, u};
19| 1.99M| for (let[v, len] : ch[u]) {
^1.00M
------------------
| Branch (19:20): [True: 66.67%, False: 33.33%]
------------------
20| 1.99M| if (v != p) {
------------------
| Branch (20:9): [True: 50.00%, False: 50.00%]
------------------
21| 999k| def res = tree_diameter(v, u);
22| 999k| res.first += len;
23| 999k| ans = std::max(ans, res);
24| 999k| }
25| 1.99M| }
26| 1.00M| return ans;
27| 1.00M|}
28| |
29| |} // namespace
30| |
31| 1|int main() {
32| 1| rd rd;
33| 1| wt wt;
34| 1| int n = rd.uh();
35| 500k| for (int i = 1; i < n; ++i) {
^499k
------------------
| Branch (35:19): [True: 100.00%, False: 0.00%]
------------------
36| 499k| int a = rd.uh();
37| 499k| int b = rd.uh();
38| 499k| int c = rd.uw();
39| 499k| ch[a].emplace_back(b, c);
40| 499k| ch[b].emplace_back(a, c);
41| 499k| }
42| 1| let[_, u] = tree_diameter(0, -1);
43| 1| let[d, v] = tree_diameter(u, -1);
44| 1| int c = 0;
45| 51| for (int i = v; i != -1; i = pa[i]) ++c;
^50 ^50
------------------
| Branch (45:19): [True: 98.04%, False: 1.96%]
------------------
46| 1| wt.ud(d);
47| 1| wt.uw(c);
48| 51| for (int i = v; i != -1; i = pa[i]) wt.uw(i);
^50 ^50
------------------
| Branch (48:19): [True: 98.04%, False: 1.96%]
------------------
49| 1|#ifdef LOCAL
50| 500k| for (int i = 0; i < n; ++i) ch[i].clear();
^500k^500k
------------------
| Branch (50:19): [True: 100.00%, False: 0.00%]
------------------
51| 1|#endif
52| 1| return 0;
53| 1|}