Submit Info #2409

Problem Lang User Status Time Memory
Dynamic Tree Vertex Add Path Sum cpp rsk0315 AC 863 ms 13.82 MiB

ケース詳細
Name Status Time Memory
example_00 AC 4 ms 0.72 MiB
max_random_00 AC 863 ms 13.82 MiB
max_random_01 AC 812 ms 13.82 MiB
max_random_02 AC 839 ms 13.80 MiB
random_00 AC 499 ms 9.10 MiB
random_01 AC 572 ms 10.59 MiB
random_02 AC 291 ms 4.50 MiB
random_03 AC 352 ms 11.11 MiB
random_04 AC 151 ms 2.04 MiB
small_00 AC 3 ms 0.67 MiB
small_01 AC 3 ms 0.67 MiB
small_02 AC 2 ms 0.70 MiB

#include <cstdio> #include <cstdint> #include <cstddef> #include <cassert> #include <algorithm> #include <utility> #include <memory> #include <array> #include <vector> #include <string> #include <map> constexpr intmax_t operator ""_jd(unsigned long long n) { return n; } constexpr uintmax_t operator ""_ju(unsigned long long n) { return n; } constexpr size_t operator ""_zu(unsigned long long n) { return n; } // constexpr ptrdiff_t operator ""_td(unsigned long long n) { return n; } template <typename Tp> class link_cut_tree { public: using size_type = size_t; using difference_type = ptrdiff_t; using value_type = Tp; using reference = Tp&; using const_reference = Tp const&; private: mutable std::vector<size_type> M_parent; mutable std::array<std::vector<size_type>, 2> M_children; mutable std::vector<size_type> M_reversed; std::vector<value_type> M_value; mutable std::array<std::vector<value_type>, 2> M_folded; static const size_type S_null = -1_zu; size_type M_parent_dir(size_type cur) const { if (M_parent[cur] == S_null) return -1_zu; if (M_children[0][M_parent[cur]] == cur) return 0_zu; if (M_children[1][M_parent[cur]] == cur) return 1_zu; return -1_zu; } size_type M_zig(size_type cur, size_type dir) const { size_type par = M_parent[cur]; size_type sub = M_children[!dir][cur]; M_parent[cur] = M_parent[par]; // for parent path M_children[!dir][cur] = par; M_parent[par] = cur; M_children[dir][par] = sub; if (sub != S_null) M_parent[sub] = par; M_resolve_folded(par); M_resolve_folded(cur); return cur; } size_type M_zigzig(size_type cur, size_type dir) const { size_type par = M_parent[cur]; size_type gpar = M_parent[par]; size_type sub1 = M_children[!dir][cur]; size_type sub2 = M_children[!dir][par]; size_type gd = M_parent_dir(gpar); M_parent[cur] = M_parent[gpar]; if (gd != -1_zu) M_children[gd][M_parent[cur]] = cur; M_children[!dir][cur] = par; M_parent[par] = cur; M_children[dir][par] = sub1; if (sub1 != S_null) M_parent[sub1] = par; M_children[!dir][par] = gpar; M_parent[gpar] = par; M_children[dir][gpar] = sub2; if (sub2 != S_null) M_parent[sub2] = gpar; M_resolve_folded(gpar); M_resolve_folded(par); M_resolve_folded(cur); return cur; } size_type M_zigzag(size_type cur, size_type dir) const { size_type par = M_parent[cur]; size_type gpar = M_parent[par]; size_type sub1 = M_children[dir][cur]; size_type sub2 = M_children[!dir][cur]; size_type gd = M_parent_dir(gpar); M_parent[cur] = M_parent[gpar]; if (gd != -1_zu) M_children[gd][M_parent[cur]] = cur; M_children[dir][cur] = gpar; M_parent[gpar] = cur; M_children[!dir][cur] = par; M_parent[par] = cur; M_children[!dir][gpar] = sub1; if (sub1 != S_null) M_parent[sub1] = gpar; M_children[dir][par] = sub2; if (sub2 != S_null) M_parent[sub2] = par; M_resolve_folded(gpar); M_resolve_folded(par); M_resolve_folded(cur); return cur; } void M_resolve_folded(size_type cur) const { for (size_type i = 0; i <= 1; ++i) { size_type first = M_children[i][cur]; size_type second = M_children[!i][cur]; if (first != S_null) { M_folded[i][cur] = M_folded[i ^ M_reversed[first]][first]; } else { M_folded[i][cur] = value_type{}; } M_folded[i][cur] += M_value[cur]; if (second != S_null) M_folded[i][cur] += M_folded[i ^ M_reversed[second]][second]; } } void M_resolve_reverse(size_type cur) const { if (!M_reversed[cur]) return; M_reversed[cur] = 0; for (size_type i = 0; i <= 1; ++i) { if (M_children[i][cur] != S_null) { std::swap(M_folded[0][M_children[i][cur]], M_folded[1][M_children[i][cur]]); M_reversed[M_children[i][cur]] ^= 1; } } std::swap(M_children[0][cur], M_children[1][cur]); M_resolve_folded(cur); } size_type M_splay(size_type cur) const { if (cur == S_null) return S_null; while (true) { size_type pd = M_parent_dir(cur); if (pd == -1_zu) return M_resolve_reverse(cur), cur; size_type p = M_parent[cur]; size_type gd = M_parent_dir(p); if (gd == -1_zu) { if (M_reversed[p]) M_resolve_reverse(p), pd ^= 1; if (M_reversed[cur]) M_resolve_reverse(cur); return M_zig(cur, pd); } size_type g = M_parent[p]; if (M_reversed[g]) M_resolve_reverse(g), gd ^= 1; if (M_reversed[p]) M_resolve_reverse(p), pd ^= 1; if (M_reversed[cur]) M_resolve_reverse(cur); cur = ((gd == pd)? M_zigzig(cur, pd): M_zigzag(cur, pd)); } } private: void M_expose(size_type src) const { size_type right = S_null; for (size_type cur = src; cur != S_null; cur = M_parent[cur]) { M_splay(cur); assert(!M_reversed[cur]); M_children[1][cur] = right; M_resolve_folded(cur); right = cur; } M_splay(src); } void M_evert(size_type src) const { M_expose(src); M_reversed[src] ^= 1; M_resolve_reverse(src); } public: link_cut_tree() = default; link_cut_tree(link_cut_tree const&) = delete; // ! link_cut_tree(link_cut_tree&&) = default; link_cut_tree& operator =(link_cut_tree const&) = delete; // ! link_cut_tree& operator =(link_cut_tree&&) = default; template <typename... Args> size_type emplace(Args&&... args) { size_type res = M_parent.size(); M_parent.push_back(S_null); M_children[0].push_back(S_null); M_children[1].push_back(S_null); M_reversed.push_back(0); M_value.emplace_back(std::forward<Args>(args)...); M_folded[0].emplace_back(); M_folded[1].emplace_back(); return res; } size_type insert() { return emplace(); } size_type insert(const_reference value) { return emplace(value); } size_type insert(value_type&& value) { return emplace(std::move(value)); } void link(size_type cur, size_type par) { M_evert(cur); M_expose(par); M_parent[cur] = par; M_children[1][par] = cur; M_resolve_folded(par); } void cut(size_type cur) { M_expose(cur); size_type par = M_children[0][cur]; M_parent[par] = S_null; M_children[0][cur] = S_null; M_resolve_folded(cur); } void evert(size_type pos) const { M_evert(pos); } void expose(size_type pos) const { M_expose(pos); } void update(size_type pos, const_reference value) { evert(pos); M_value[pos] = value; M_resolve_folded(pos); } void update(size_type pos, value_type&& value) { evert(pos); M_value[pos] = std::move(value); M_resolve_folded(pos); } value_type fold_path(size_type src, size_type dst) const { M_evert(src); M_expose(dst); return M_folded[0][dst]; } const_reference operator [](size_type n) const { return M_value[n]; } }; template <typename Tp> const typename link_cut_tree<Tp>::size_type link_cut_tree<Tp>::S_null; int main() { size_t n, q; scanf("%zu %zu", &n, &q); std::vector<intmax_t> a(n); for (auto& ai: a) scanf("%jd", &ai); link_cut_tree<intmax_t> lct; for (size_t i = 0; i < n; ++i) { lct.insert(a[i]); } for (size_t i = 1; i < n; ++i) { size_t u, v; scanf("%zu %zu", &u, &v); lct.link(u, v); } for (size_t i = 0; i < q; ++i) { int t; scanf("%d", &t); if (t == 0) { // 0 u v w x size_t u, v, w, x; scanf("%zu %zu %zu %zu", &u, &v, &w, &x); lct.evert(u); lct.expose(v); lct.cut(v); lct.link(w, x); } else if (t == 1) { // 1 p x size_t p; intmax_t x; scanf("%zu %jd", &p, &x); lct.update(p, lct[p]+x); } else if (t == 2) { // 2 u v size_t u, v; scanf("%zu %zu", &u, &v); printf("%jd\n", lct.fold_path(u, v)); } } }