src/tree/dfs/height/lib.hpp
| Line | Branch | Exec | Source |
|---|---|---|---|
| 1 | #pragma once | ||
| 2 | |||
| 3 | #include "../../../util/alias/others/lib.hpp" | ||
| 4 | #include "../../ds/lib.hpp" | ||
| 5 | |||
| 6 | namespace tifa_libs { | ||
| 7 | |||
| 8 | template <tree_c G> | ||
| 9 | 32 | CEXP auto tree_height(G CR tr) NE { | |
| 10 | using T = TPN G::Et; | ||
| 11 | 32 | cu32 n = tr.vsize(); | |
| 12 | 32 | vvec<T> _(n); | |
| 13 |
2/2✓ Branch 4 taken 208727 times.
✓ Branch 5 taken 32 times.
|
208759 | flt_ (u32, i, 0, n) _[i].resize(tr[i].size(), T(-1)); |
| 14 | 32 | auto f = [&](auto&& f, u32 u, u32 fa) NE -> T { | |
| 15 | 626117 | T ans = 0; | |
| 16 | 626117 | auto&& es = tr[u]; | |
| 17 |
2/2✓ Branch 1 taken 601080016 times.
✓ Branch 2 taken 626117 times.
|
601706133 | flt_ (u32, i, 0, (u32)es.size()) |
| 18 | if CEXP (wtree_c<G>) { | ||
| 19 |
4/4✓ Branch 1 taken 600662626 times.
✓ Branch 2 taken 417390 times.
✓ Branch 5 taken 417390 times.
✓ Branch 6 taken 600245236 times.
|
601080016 | if (auto&& [v, w] = es[i]; v != fa) ans = max(ans, (_[u][i] = (_[u][i] == T(-1) ? f(f, v, u) : _[u][i])) + w); |
| 20 | } else if (auto v = es[i]; v != fa) ans = max(ans, (_[u][i] = (_[u][i] == T(-1) ? f(f, v, u) : _[u][i])) + 1); | ||
| 21 | 626117 | return ans; | |
| 22 | }; | ||
| 23 | 32 | vec<T> h(n); | |
| 24 |
2/2✓ Branch 2 taken 208727 times.
✓ Branch 3 taken 32 times.
|
208759 | flt_ (u32, i, 0, n) h[i] = f(f, i, i); |
| 25 | 32 | return h; | |
| 26 | 32 | } | |
| 27 | |||
| 28 | } // namespace tifa_libs | ||
| 29 |