test/cpv/library-checker-tree/vertex_add_subtree_sum.dsu_on_tree.cpp
| Line | Branch | Exec | Source |
|---|---|---|---|
| 1 | // competitive-verifier: PROBLEM https://judge.yosupo.jp/problem/vertex_add_subtree_sum | ||
| 2 | #include "../../../src/ds/fenwick/d1/lib.hpp" | ||
| 3 | #include "../../../src/graph/ds/alist/lib.hpp" | ||
| 4 | #include "../../../src/io/fastin/lib.hpp" | ||
| 5 | #include "../../../src/io/fastout/lib.hpp" | ||
| 6 | #include "../../../src/tree/dfs/info/lib.hpp" | ||
| 7 | #include "../../../src/tree/ds/lib.hpp" | ||
| 8 | #include "../../../src/tree/dsu_on_tree/lib.hpp" | ||
| 9 | |||
| 10 | using namespace tifa_libs; | ||
| 11 | CEXP i64 INF = std::numeric_limits<i64>::max() / 2; | ||
| 12 | |||
| 13 | 16 | int main() { | |
| 14 | u32 n, q; | ||
| 15 | 16 | fin_uint >> n >> q; | |
| 16 |
1/2✓ Branch 1 taken 16 times.
✗ Branch 2 not taken.
|
16 | vecii a(n); |
| 17 |
2/2✓ Branch 6 taken 4115189 times.
✓ Branch 7 taken 16 times.
|
4115205 | for (auto& x : a) fin_uint >> x; |
| 18 | 16 | tree<alist<>> tr(n); | |
| 19 |
2/2✓ Branch 3 taken 4115173 times.
✓ Branch 4 taken 16 times.
|
4115189 | for (u32 i = 1, p; i < n; ++i) fin_uint >> p, tr.add_arc((u32)p, (u32)i), tr.add_arc((u32)i, (u32)p); |
| 20 | |||
| 21 |
1/2✓ Branch 1 taken 16 times.
✗ Branch 2 not taken.
|
32 | vvecpti upd(n); |
| 22 |
1/2✓ Branch 1 taken 16 times.
✗ Branch 2 not taken.
|
16 | vveci que(n); |
| 23 |
3/4✓ Branch 3 taken 4115189 times.
✗ Branch 4 not taken.
✓ Branch 5 taken 4115189 times.
✓ Branch 6 taken 16 times.
|
4115205 | flt_ (u32, i, 0, n) upd[i].emplace_back(0, a[i]); |
| 24 |
2/2✓ Branch 0 taken 3837215 times.
✓ Branch 1 taken 16 times.
|
3837231 | flt_ (u32, i, 1, q + 1) { |
| 25 | u32 c, u; | ||
| 26 | 3837215 | fin_uint >> c >> u; | |
| 27 |
2/2✓ Branch 0 taken 1919727 times.
✓ Branch 1 taken 1917488 times.
|
3837215 | if (c == 0) { |
| 28 | u32 x; | ||
| 29 | 1919727 | fin_uint >> x; | |
| 30 |
1/2✓ Branch 2 taken 1919727 times.
✗ Branch 3 not taken.
|
1919727 | upd[u].emplace_back(i, x); |
| 31 |
1/2✓ Branch 2 taken 1917488 times.
✗ Branch 3 not taken.
|
1917488 | } else que[u].push_back((i32)i); |
| 32 | } | ||
| 33 | |||
| 34 | 16 | fenwick<i64> bit(q + 2); | |
| 35 |
1/2✓ Branch 1 taken 16 times.
✗ Branch 2 not taken.
|
16 | vecii ans(q + 1, INF); |
| 36 | |||
| 37 | 16 | tree_dfs_info<tree<alist<>>, tdi_dfn, tdi_maxson, tdi_maxdfn, tdi_euler> info(tr); | |
| 38 | 16 | dsu_on_tree( | |
| 39 | tr, info.dfn, info.sz, info.maxson, info.maxdfn, info.euler, | ||
| 40 | 18410498 | [&](u32 i) { | |
| 41 |
2/2✓ Branch 9 taken 26724587 times.
✓ Branch 10 taken 18410466 times.
|
45135053 | for (auto&& [j, x] : upd[i]) bit.add(u32(j + 1), x); |
| 42 | 18410466 | }, | |
| 43 | 4115221 | [&](u32 i) { | |
| 44 |
2/2✓ Branch 8 taken 1917488 times.
✓ Branch 9 taken 4115189 times.
|
6032677 | for (auto&& j : que[i]) ans[(u32)j] = bit.sum(u32(j + 1)); |
| 45 | 4115189 | }, | |
| 46 | 16 | [&](u32 i) { | |
| 47 |
2/2✓ Branch 9 taken 26724587 times.
✓ Branch 10 taken 18410466 times.
|
45135053 | for (auto&& [j, x] : upd[i]) bit.add(u32(j + 1), -x); |
| 48 | 18410466 | }, | |
| 49 | 1558491 | []() {}); | |
| 50 |
2/2✓ Branch 5 taken 3837231 times.
✓ Branch 6 taken 16 times.
|
3837247 | for (auto&& i : ans) |
| 51 |
2/2✓ Branch 0 taken 1917488 times.
✓ Branch 1 taken 1919743 times.
|
3837231 | if (i != INF) fout << i << '\n'; |
| 52 | 16 | return 0; | |
| 53 | 16 | } | |
| 54 |