Submit Info #2392

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

ケース詳細
Name Status Time Memory
example_00 AC 2 ms 0.68 MiB
max_random_00 AC 929 ms 39.58 MiB
max_random_01 AC 889 ms 39.66 MiB
max_random_02 AC 915 ms 39.67 MiB
random_00 AC 586 ms 25.55 MiB
random_01 AC 647 ms 30.05 MiB
random_02 AC 315 ms 11.32 MiB
random_03 AC 416 ms 32.60 MiB
random_04 AC 189 ms 3.81 MiB
small_00 AC 2 ms 0.80 MiB
small_01 AC 2 ms 0.70 MiB
small_02 AC 3 ms 0.67 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: class node; using pointer = std::shared_ptr<node>; class node { friend 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: using pointer = std::shared_ptr<node>; mutable pointer M_parent = nullptr; mutable std::array<pointer, 2> M_children{{nullptr, nullptr}}; mutable size_type M_reversed = false; value_type M_value{}; mutable std::array<value_type, 2> M_folded{{value_type{}, value_type{}}}; public: node() = default; node(node const&) = delete; // ! node(node&&) = default; node(const_reference value): M_value(value), M_folded{{value, value}} {} node(value_type&& value): M_value(std::move(value)), M_folded{{M_value, M_value}} {} }; static size_type S_parent_dir(pointer ptr) { if (!ptr->M_parent) return -1_zu; if (ptr->M_parent->M_children[0] == ptr) return 0; if (ptr->M_parent->M_children[1] == ptr) return 1; return -1_zu; } static pointer S_zig(pointer cur, size_type dir) { pointer par = cur->M_parent; pointer sub = cur->M_children[!dir]; cur->M_parent = par->M_parent; // for parent path cur->M_children[!dir] = par; par->M_parent = cur; par->M_children[dir] = sub; if (sub) sub->M_parent = par; S_resolve_folded(par); S_resolve_folded(cur); return cur; } static pointer S_zigzig(pointer cur, size_type dir) { pointer par = cur->M_parent; pointer gpar = par->M_parent; pointer sub1 = cur->M_children[!dir]; pointer sub2 = par->M_children[!dir]; size_type gd = S_parent_dir(gpar); cur->M_parent = gpar->M_parent; if (gd != -1_zu) cur->M_parent->M_children[gd] = cur; cur->M_children[!dir] = par; par->M_parent = cur; par->M_children[dir] = sub1; if (sub1) sub1->M_parent = par; par->M_children[!dir] = gpar; gpar->M_parent = par; gpar->M_children[dir] = sub2; if (sub2) sub2->M_parent = gpar; S_resolve_folded(gpar); S_resolve_folded(par); S_resolve_folded(cur); return cur; } static pointer S_zigzag(pointer cur, size_type dir) { pointer par = cur->M_parent; pointer gpar = par->M_parent; pointer sub1 = cur->M_children[dir]; pointer sub2 = cur->M_children[!dir]; size_type gd = S_parent_dir(gpar); cur->M_parent = gpar->M_parent; if (gd != -1_zu) cur->M_parent->M_children[gd] = cur; cur->M_children[dir] = gpar; gpar->M_parent = cur; cur->M_children[!dir] = par; par->M_parent = cur; gpar->M_children[!dir] = sub1; if (sub1) sub1->M_parent = gpar; par->M_children[dir] = sub2; if (sub2) sub2->M_parent = par; S_resolve_folded(gpar); S_resolve_folded(par); S_resolve_folded(cur); return cur; } static void S_resolve_folded(pointer cur) { for (size_type i = 0; i <= 1; ++i) { pointer& first = cur->M_children[i]; pointer& second = cur->M_children[!i]; if (first) { cur->M_folded[i] = first->M_folded[i ^ first->M_reversed]; } else { cur->M_folded[i] = value_type{}; } cur->M_folded[i] += cur->M_value; if (second) cur->M_folded[i] += second->M_folded[i ^ second->M_reversed]; } } static void S_resolve_reverse(pointer cur) { if (!cur->M_reversed) return; cur->M_reversed = 0; for (size_type i = 0; i <= 1; ++i) { if (cur->M_children[i]) { std::swap(cur->M_children[i]->M_folded[0], cur->M_children[i]->M_folded[1]); cur->M_children[i]->M_reversed ^= 1; } } std::swap(cur->M_children[0], cur->M_children[1]); S_resolve_folded(cur); } static pointer S_splay(pointer cur) { if (!cur) return nullptr; while (true) { size_type pd = S_parent_dir(cur); if (pd == -1_zu) return S_resolve_reverse(cur), cur; pointer p = cur->M_parent; size_type gd = S_parent_dir(p); if (gd == -1_zu) { if (p->M_reversed) S_resolve_reverse(p), pd ^= 1; if (cur->M_reversed) S_resolve_reverse(cur); return S_zig(cur, pd); } pointer g = p->M_parent; if (g->M_reversed) S_resolve_reverse(g), gd ^= 1; if (p->M_reversed) S_resolve_reverse(p), pd ^= 1; if (cur->M_reversed) S_resolve_reverse(cur); cur = ((gd == pd)? S_zigzig(cur, pd): S_zigzag(cur, pd)); } } private: static void S_expose(pointer src) { pointer right = nullptr; for (pointer cur = src; cur; cur = cur->M_parent) { S_splay(cur); assert(!cur->M_reversed); cur->M_children[1] = right; S_resolve_folded(cur); right = cur; } S_splay(src); } static void S_evert(pointer src) { S_expose(src); src->M_reversed ^= 1; S_resolve_reverse(src); } std::map<pointer, size_t> M_index; std::string M_node_name(pointer pos) const { auto it = M_index.find(pos); if (it == M_index.end()) return "(nil)"; char buf[128] = {}; snprintf(buf, sizeof buf, "[%zu] (%p)", it->second, pos.get()); return buf; } 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; class node_handle { friend link_cut_tree; pointer M_ptr = nullptr; node_handle(pointer ptr): M_ptr(ptr) {} public: node_handle() = default; node_handle(node_handle const&) = default; node_handle(node_handle&&) = default; node_handle& operator =(node_handle const&) = default; node_handle& operator =(node_handle&&) = default; const_reference& operator *() const { return M_ptr->M_value; } }; node_handle add_node() { return std::make_shared<node>(); } node_handle add_node(const_reference value) { pointer res = std::make_shared<node>(value); size_type i = M_index.size(); M_index[res] = i++; return res; // return std::make_shared<node>(value); } node_handle add_node(value_type&& value) { pointer res = std::make_shared<node>(std::move(value)); size_type i = M_index.size(); M_index[res] = i++; return res; // return std::make_shared<node>(std::move(value)); } void link(node_handle curh, node_handle parh) { pointer cur = curh.M_ptr; pointer par = parh.M_ptr; S_evert(cur); S_expose(par); cur->M_parent = par; par->M_children[1] = cur; S_resolve_folded(par); } void cut(node_handle curh) { pointer cur = curh.M_ptr; S_expose(cur); pointer par = cur->M_children[0]; par->M_parent = nullptr; cur->M_children[0] = nullptr; S_resolve_folded(cur); } void evert(node_handle posh) const { S_evert(posh.M_ptr); } void expose(node_handle posh) const { S_expose(posh.M_ptr); } void update(node_handle posh, const_reference value) { evert(posh); pointer pos = posh.M_ptr; pos->M_value = value; S_resolve_folded(pos); } void update(node_handle posh, value_type&& value) { evert(posh); pointer pos = posh.M_ptr; pos->M_value = std::move(value); S_resolve_folded(pos); } value_type fold_path(node_handle srch, node_handle dsth) { pointer src = srch.M_ptr; pointer dst = dsth.M_ptr; S_evert(src); // fprintf(stderr, "fold_path(%zu, %zu), everted:\n", M_index.at(src), M_index.at(dst)); // for (auto const& p: M_index) inspect(p.first); S_expose(dst); // fprintf(stderr, "---\n"); // fprintf(stderr, "fold_path, exposed:\n"); // for (auto const& p: M_index) inspect(p.first); // fprintf(stderr, "------\n"); return dst->M_folded[0]; } void inspect(node_handle posh) const { pointer pos = posh.M_ptr; // pos != nullptr fprintf(stderr, "%s:\n", M_node_name(pos).c_str()); fprintf(stderr, " left: %s\n", M_node_name(pos->M_children[0]).c_str()); fprintf(stderr, " right: %s\n", M_node_name(pos->M_children[1]).c_str()); fprintf(stderr, " parent: %s\n", M_node_name(pos->M_parent).c_str()); fprintf(stderr, " reversed? %s\n", pos->M_reversed? "Yes": "No"); fprintf(stderr, " folded: %jd\n", pos->M_folded[pos->M_reversed]); } }; int main() { using node_handle = typename link_cut_tree<intmax_t>::node_handle; 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; std::vector<node_handle> nh(n); for (size_t i = 0; i < n; ++i) { nh[i] = lct.add_node(a[i]); } // fprintf(stderr, "---\n"); // for (size_t i = 0; i < n; ++i) // lct.inspect(nh[i]); // fprintf(stderr, "---\n"); for (size_t i = 1; i < n; ++i) { size_t u, v; scanf("%zu %zu", &u, &v); // fprintf(stderr, "link: %zu <-> %zu\n", u, v); lct.link(nh[u], nh[v]); // for (size_t j = 0; j < n; ++j) // lct.inspect(nh[j]); // fprintf(stderr, "------\n"); } 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(nh[u]); lct.expose(nh[v]); lct.cut(nh[v]); lct.link(nh[w], nh[x]); } else if (t == 1) { // 1 p x size_t p; intmax_t x; scanf("%zu %jd", &p, &x); lct.update(nh[p], *nh[p]+x); } else if (t == 2) { // 2 u v size_t u, v; scanf("%zu %zu", &u, &v); printf("%jd\n", lct.fold_path(nh[u], nh[v])); } } }