src/tree/lca_linear/lib.hpp
| Line | Branch | Exec | Source |
|---|---|---|---|
| 1 | #pragma once | ||
| 2 | |||
| 3 | #include "../../bit/lowbit/lib.hpp" | ||
| 4 | #include "../../graph/ds/graph_c/lib.hpp" | ||
| 5 | |||
| 6 | namespace tifa_libs { | ||
| 7 | |||
| 8 | template <graph_c G> | ||
| 9 | class lca_linear { | ||
| 10 | vecu d, in, asc, head; | ||
| 11 | |||
| 12 | public: | ||
| 13 | 200 | CEXPE lca_linear(G CR g) NE : d(g.vsize()), in(g.vsize()), asc(g.vsize()), head(g.vsize() + 1) { | |
| 14 | 25 | vecptu ord; | |
| 15 | 10224927 | auto dfs = [&](auto&& f, u32 u, u32 p) -> void { | |
| 16 | 10224927 | ord.emplace_back(u, p); | |
| 17 |
2/2✓ Branch 9 taken 20449804 times.
✓ Branch 10 taken 10224927 times.
|
30674731 | for (in[u] = (u32)ord.size(); u32 v : g[u]) |
| 18 |
2/2✓ Branch 0 taken 10224902 times.
✓ Branch 1 taken 10224902 times.
|
20449804 | if (v != p) |
| 19 |
3/4✓ Branch 3 taken 10224902 times.
✗ Branch 4 not taken.
✓ Branch 11 taken 7441424 times.
✓ Branch 12 taken 2783478 times.
|
10224902 | if (d[v] = 1 + d[u], f(f, v, u), head[in[v]] = u; lowbit(in[u]) < lowbit(in[v])) in[u] = in[v]; |
| 20 | }; | ||
| 21 | 25 | dfs(dfs, 0, 0); | |
| 22 |
2/2✓ Branch 11 taken 10224927 times.
✓ Branch 12 taken 25 times.
|
10224952 | for (auto [u, p] : ord) asc[u] = asc[p] | lowbit(in[u]); |
| 23 | 25 | } | |
| 24 | |||
| 25 | 9662271 | CEXP u32 operator()(u32 u, u32 v) CNE { | |
| 26 |
2/2✓ Branch 2 taken 8324826 times.
✓ Branch 3 taken 1337445 times.
|
9662271 | if (u32 j = in[u] ^ in[v]) { |
| 27 | 8324826 | j = asc[u] & asc[v] & -std::bit_floor(j); | |
| 28 |
2/2✓ Branch 2 taken 6330259 times.
✓ Branch 3 taken 1994567 times.
|
8324826 | if (auto k = std::bit_floor(asc[u] ^ j)) u = head[(in[u] & -k) | k]; |
| 29 |
2/2✓ Branch 2 taken 8121503 times.
✓ Branch 3 taken 203323 times.
|
8324826 | if (auto k = std::bit_floor(asc[v] ^ j)) v = head[(in[v] & -k) | k]; |
| 30 | } | ||
| 31 |
2/2✓ Branch 2 taken 7059311 times.
✓ Branch 3 taken 2602960 times.
|
9662271 | retif_((d[u] < d[v]), u, v); |
| 32 | } | ||
| 33 | }; | ||
| 34 | |||
| 35 | } // namespace tifa_libs | ||
| 36 |