src/tree/dsu_on_tree/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 | // @param update(now): update data of node %now | ||
| 9 | // @param query(now): answer queries of subtree %now | ||
| 10 | // @param clear(now): reset data of node %now (if necessary) | ||
| 11 | // @param reset(): reset data related to all (if necessary) | ||
| 12 | template <class Fu, class Fq, class Fc, class Fr> | ||
| 13 | requires requires(Fu update, Fq query, Fc clear, Fr reset, u32 now) { | ||
| 14 | update(now); | ||
| 15 | query(now); | ||
| 16 | clear(now); | ||
| 17 | reset(); | ||
| 18 | } | ||
| 19 | 16 | CEXP void dsu_on_tree(tree_c auto CR tr, spnu dfn, spnu sz, spnu maxson, spnu maxdfn, spnu euler, Fu&& update, Fq&& query, Fc&& clear, Fr&& reset) NE { | |
| 20 | 4115205 | auto f = [&](auto&& f, u32 now, u32 fa = -1_u32, bool keep = false) NE -> void { | |
| 21 |
2/2✓ Branch 6 taken 8230346 times.
✓ Branch 7 taken 4115189 times.
|
12345535 | for (auto v : tr[now]) |
| 22 |
6/6✓ Branch 1 taken 4115173 times.
✓ Branch 2 taken 4115173 times.
✓ Branch 5 taken 1558459 times.
✓ Branch 6 taken 2556714 times.
✓ Branch 7 taken 1558459 times.
✓ Branch 8 taken 6671887 times.
|
8230346 | if ((u32)v != fa && (u32)v != maxson[now]) f(f, (u32)v, now, false); |
| 23 |
2/2✓ Branch 1 taken 2556714 times.
✓ Branch 2 taken 1558475 times.
|
4115189 | if (sz[now] > 1) f(f, maxson[now], now, true); |
| 24 |
2/2✓ Branch 6 taken 8230346 times.
✓ Branch 7 taken 4115189 times.
|
12345535 | for (auto v : tr[now]) |
| 25 |
6/6✓ Branch 1 taken 4115173 times.
✓ Branch 2 taken 4115173 times.
✓ Branch 5 taken 1558459 times.
✓ Branch 6 taken 2556714 times.
✓ Branch 7 taken 1558459 times.
✓ Branch 8 taken 6671887 times.
|
8230346 | if ((u32)v != fa && (u32)v != maxson[now]) |
| 26 |
2/2✓ Branch 6 taken 14295277 times.
✓ Branch 7 taken 1558459 times.
|
15853736 | flt_ (u32, i, dfn[(u32)v], maxdfn[(u32)v] + 1) update(euler[i]); |
| 27 | 4115189 | update(now), query(now); | |
| 28 |
2/2✓ Branch 0 taken 1558475 times.
✓ Branch 1 taken 2556714 times.
|
4115189 | if (!keep) { |
| 29 |
2/2✓ Branch 4 taken 18410466 times.
✓ Branch 5 taken 1558475 times.
|
19968941 | flt_ (u32, i, dfn[now], maxdfn[now] + 1) clear(euler[i]); |
| 30 | 1558475 | reset(); | |
| 31 | } | ||
| 32 | 4115189 | return; | |
| 33 | }; | ||
| 34 | 16 | f(f, tr.root); | |
| 35 | 16 | } | |
| 36 | |||
| 37 | } // namespace tifa_libs | ||
| 38 |