src/tree/virtual_tree/lib.hpp
| Line | Branch | Exec | Source |
|---|---|---|---|
| 1 | #pragma once | ||
| 2 | |||
| 3 | #include "../../graph/ds/alist/lib.hpp" | ||
| 4 | #include "../ds/lib.hpp" | ||
| 5 | #include "../lca_hld/lib.hpp" | ||
| 6 | |||
| 7 | namespace tifa_libs { | ||
| 8 | |||
| 9 | template <tree_c G> | ||
| 10 | class virtual_tree { | ||
| 11 | u32 root, tim{0}; | ||
| 12 | lca_hld<G> lca_; | ||
| 13 | vecu st, used, vis; | ||
| 14 | |||
| 15 | 17889339 | CEXP void touch(u32 x) NE { | |
| 16 |
2/2✓ Branch 1 taken 11552442 times.
✓ Branch 2 taken 6336897 times.
|
17889339 | if (vis[x] == tim) return; |
| 17 | 6336897 | vis[x] = tim, used.push_back(x); | |
| 18 | } | ||
| 19 | 5776221 | CEXP void add_arc_(u32 u, u32 v) NE { vt.add_arc(u, v), touch(u), touch(v); } | |
| 20 | |||
| 21 | 3833872 | CEXP void insert(u32 x) NE { | |
| 22 | 3833872 | touch(x); | |
| 23 | 3833872 | cu32 lca = lca_(x, st.back()); | |
| 24 |
2/2✓ Branch 1 taken 799090 times.
✓ Branch 2 taken 3034782 times.
|
3833872 | if (lca == st.back()) return st.push_back(x); |
| 25 |
6/6✓ Branch 6 taken 5307879 times.
✓ Branch 7 taken 752446 times.
✓ Branch 12 taken 3025543 times.
✓ Branch 13 taken 2282336 times.
✓ Branch 14 taken 3025543 times.
✓ Branch 15 taken 3034782 times.
|
6060325 | while (st.size() > 1 && lca_.info.dep[st[st.size() - 2]] >= lca_.info.dep[lca]) add_arc_(st[st.size() - 2], st.back()), st.pop_back(); |
| 26 |
2/2✓ Branch 3 taken 1942349 times.
✓ Branch 4 taken 1092433 times.
|
3034782 | if (lca_.info.dep[st.back()] > lca_.info.dep[lca]) add_arc_(lca, st.back()), st.pop_back(); |
| 27 |
2/2✓ Branch 1 taken 1942349 times.
✓ Branch 2 taken 1092433 times.
|
3034782 | if (st.back() != lca) touch(lca), st.push_back(lca); |
| 28 | 3034782 | st.push_back(x); | |
| 29 | } | ||
| 30 | |||
| 31 | public: | ||
| 32 | using tree_info_t = lca_hld<G>::tree_info_t; | ||
| 33 | tree<alist<>> vt; | ||
| 34 | |||
| 35 | 30 | CEXPE virtual_tree(G CR tr) NE : root{tr.root}, lca_(tr), st{}, used{}, vis(tr.vsize()), vt(tr.vsize()) {} | |
| 36 | |||
| 37 | 560676 | CEXP void build(vecu& a) NE { | |
| 38 |
2/2✓ Branch 7 taken 6336639 times.
✓ Branch 8 taken 560676 times.
|
6897315 | for (++tim; cu32 x : used) vt[x].clear(); |
| 39 | 560676 | used.clear(), st.clear(); | |
| 40 | 25479701 | sort(a, [&](u32 a, u32 b) NE { return lca_.info.dfn[a] < lca_.info.dfn[b]; }); | |
| 41 |
2/2✓ Branch 8 taken 3833872 times.
✓ Branch 9 taken 560676 times.
|
4394548 | for (st.push_back(root), touch(root); cu32 x : a) insert(x); |
| 42 |
2/2✓ Branch 6 taken 808329 times.
✓ Branch 7 taken 560676 times.
|
1369005 | while (st.size() > 1) add_arc_(st[st.size() - 2], st.back()), st.pop_back(); |
| 43 | 560676 | st.pop_back(); | |
| 44 | 560676 | } | |
| 45 | }; | ||
| 46 | |||
| 47 | } // namespace tifa_libs | ||
| 48 |