src/tree/dfs/diam/lib.hpp
| Line | Branch | Exec | Source |
|---|---|---|---|
| 1 | #pragma once | ||
| 2 | |||
| 3 | #include "../info/lib.hpp" | ||
| 4 | |||
| 5 | namespace tifa_libs { | ||
| 6 | |||
| 7 | // {u, v, diam} | ||
| 8 | template <tree_c G> | ||
| 9 | 16 | CEXP auto tree_diam(G& tree) NE { | |
| 10 | 16 | auto _ = tree.root; | |
| 11 | 16 | auto d = tree_dfs_info<G, tdi_dis<G>>(tree).dis; | |
| 12 | 16 | cu32 u = tree.root = u32(max_element(d) - begin(d)); | |
| 13 | 16 | d = tree_dfs_info<G, tdi_dis<G>>(tree).dis; | |
| 14 | 16 | cu32 v = u32(max_element(d) - begin(d)); | |
| 15 | 16 | tree.root = _; | |
| 16 | 16 | return std::make_tuple(u, v, d[v]); | |
| 17 | 16 | } | |
| 18 | // diam | ||
| 19 | template <tree_c G> | ||
| 20 | 32 | CEXP auto tree_diam_d(G CR tree) NE { | |
| 21 | using T = TPN G::Et; | ||
| 22 | 32 | vec<T> mdis(tree.vsize()); | |
| 23 | 32 | T d = 0; | |
| 24 | 1013812 | auto dfs = [&](auto&& dfs, u32 u, u32 fa) NE -> void { | |
| 25 | if CEXP (wtree_c<G>) { | ||
| 26 |
2/2✓ Branch 6 taken 1013716 times.
✓ Branch 7 taken 506890 times.
|
1520606 | for (auto [v, w] : tree[u]) |
| 27 |
2/2✓ Branch 0 taken 506858 times.
✓ Branch 1 taken 506858 times.
|
1013716 | if (v != fa) dfs(dfs, v, u), d = max(d, mdis[u] + mdis[v] + w), mdis[u] = max(mdis[u], mdis[v] + w); |
| 28 | ; | ||
| 29 | } else | ||
| 30 | for (auto v : tree[u]) | ||
| 31 | if ((u32)v != fa) dfs(dfs, (u32)v, u), d = max(d, mdis[u] + mdis[v] + 1), mdis[u] = max(mdis[u], mdis[v] + 1); | ||
| 32 | }; | ||
| 33 | 32 | dfs(dfs, tree.root, -1_u32); | |
| 34 | 64 | return d; | |
| 35 | 32 | } | |
| 36 | |||
| 37 | } // namespace tifa_libs | ||
| 38 |