結果
問題 | No.2163 LCA Sum Query |
ユーザー | noshi91 |
提出日時 | 2022-12-14 00:50:55 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
RE
|
実行時間 | - |
コード長 | 24,101 bytes |
コンパイル時間 | 2,079 ms |
コンパイル使用メモリ | 127,944 KB |
実行使用メモリ | 35,136 KB |
最終ジャッジ日時 | 2024-11-07 18:04:16 |
合計ジャッジ時間 | 19,639 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
5,248 KB |
testcase_01 | AC | 2 ms
5,248 KB |
testcase_02 | RE | - |
testcase_03 | RE | - |
testcase_04 | RE | - |
testcase_05 | RE | - |
testcase_06 | RE | - |
testcase_07 | RE | - |
testcase_08 | RE | - |
testcase_09 | RE | - |
testcase_10 | RE | - |
testcase_11 | RE | - |
testcase_12 | RE | - |
testcase_13 | RE | - |
testcase_14 | RE | - |
testcase_15 | RE | - |
testcase_16 | RE | - |
testcase_17 | RE | - |
testcase_18 | RE | - |
testcase_19 | RE | - |
testcase_20 | RE | - |
testcase_21 | RE | - |
testcase_22 | AC | 618 ms
29,880 KB |
testcase_23 | RE | - |
testcase_24 | AC | 610 ms
29,884 KB |
testcase_25 | RE | - |
testcase_26 | AC | 512 ms
29,760 KB |
testcase_27 | RE | - |
testcase_28 | AC | 508 ms
29,796 KB |
testcase_29 | RE | - |
testcase_30 | AC | 366 ms
34,360 KB |
testcase_31 | RE | - |
testcase_32 | AC | 362 ms
33,084 KB |
testcase_33 | RE | - |
testcase_34 | AC | 294 ms
30,060 KB |
testcase_35 | AC | 356 ms
29,792 KB |
testcase_36 | AC | 286 ms
30,004 KB |
testcase_37 | AC | 343 ms
30,104 KB |
testcase_38 | AC | 396 ms
31,680 KB |
testcase_39 | RE | - |
testcase_40 | AC | 408 ms
31,316 KB |
testcase_41 | RE | - |
ソースコード
#include <array> #include <cassert> #include <utility> #include <variant> #include <vector> /* struct Info { using V; using E; using Point; using Path; static Point rake(Point, Point); static Point id(); static Path to_path(V, Point); static Path compress(Path, E, Path); static Path reverse(Path); static Point to_point(E, Path); }; */ template <class Info> class top_tree { using V = typename Info::V; using E = typename Info::E; using Point = typename Info::Point; using Path = typename Info::Path; struct node_type; using node_ptr = node_type*; struct vertex_node { V v; Path path; vertex_node(V v_, Path path_) : v(std::move(v_)), path(std::move(path_)) {} }; struct solid_edge_node { bool rev; E e; Path sum; solid_edge_node(E e_, Path sum_) : rev(false), e(std::move(e_)), sum(std::move(sum_)) {} }; struct dashed_edge_node { E e; Point point; Point sum; dashed_edge_node(E e_, Point point_, Point sum_) : e(std::move(e_)), point(std::move(point_)), sum(std::move(sum_)) {} }; using data_variant = std::variant<vertex_node, solid_edge_node, dashed_edge_node>; struct node_type { node_ptr p; std::array<node_ptr, 3> c; data_variant data; template <class... Args> node_type(Args &&... args) : p(nullptr), c({ nullptr, nullptr, nullptr }), data(std::forward<Args>(args)...) {} }; static void link_child(node_type& par, const node_ptr ch, const int dir) { par.c[dir] = ch; if (ch) { ch->p = ∥ } } static int get_dir(const node_type& node) { if (node.p) { for (int i = 0; i < 3; i++) { if (node.p->c[i] == &node) { return i; } } assert(false); } else { return 1; } } static void p_replace(node_type& prev, node_type& n) { if (prev.p) { prev.p->c[get_dir(prev)] = &n; n.p = prev.p; } else { n.p = nullptr; } } static Point get_sum_point(const node_ptr ptr) { if (ptr) { return std::get<dashed_edge_node>(ptr->data).sum; } else { return Info::id(); } } static const Path& get_sum_path(const node_type& node) { struct { const Path& operator()(const vertex_node& v) const { return v.path; } const Path& operator()(const solid_edge_node& s) const { return s.sum; } const Path& operator()(const dashed_edge_node&) const { throw "top_tree: internal error"; } } visitor{}; return std::visit(visitor, node.data); } static void update(node_type& node) { struct { node_type& node; void operator()(vertex_node&) const { throw "top_tree: internal error"; } void operator()(solid_edge_node& s) const { s.sum = Info::compress(get_sum_path(*node.c[0]), s.e, get_sum_path(*node.c[2])); } void operator()(dashed_edge_node& d) const { d.sum = Info::rake(d.point, Info::rake(get_sum_point(node.c[0]), get_sum_point(node.c[2]))); } } visitor{ node }; std::visit(visitor, node.data); } static void rotate(node_type& node, const int dir) { node_type& ch = *node.c[dir ^ 2]; ch.p = node.p; if (node.p) { node.p->c[get_dir(node)] = &ch; } link_child(node, ch.c[dir], dir ^ 2); update(node); link_child(ch, &node, dir); } static void splay(node_type& node) { while (true) { const int d0 = get_dir(node); if (d0 == 1) { break; } node_type& p = *node.p; const int d1 = get_dir(p); if (d1 == 1) { rotate(p, d0 ^ 2); break; } node_type& pp = *p.p; if (d0 == d1) { rotate(pp, d1 ^ 2); rotate(p, d0 ^ 2); } else { rotate(p, d0 ^ 2); rotate(pp, d1 ^ 2); } } update(node); } static void reverse(node_type& node) { struct { void operator()(vertex_node&) const {} void operator()(solid_edge_node& s) const { s.sum = Info::reverse(std::move(s.sum)); s.rev = !s.rev; } void operator()(dashed_edge_node&) const { throw "top_tree: internal error"; } } visitor{}; std::visit(visitor, node.data); } static void propagate(node_type& node) { if (node.p) { propagate(*node.p); } struct { node_type& node; void operator()(vertex_node&) const {} void operator()(solid_edge_node& s) const { if (s.rev) { s.rev = false; std::swap(node.c[0], node.c[2]); reverse(*node.c[0]); reverse(*node.c[2]); } } void operator()(dashed_edge_node&) const {} } visitor{ node }; std::visit(visitor, node.data); } static node_ptr merge(const node_ptr x, node_ptr y) { if (!y) { return x; } y->p = nullptr; while (y->c[0]) { y = y->c[0]; } link_child(*y, x, 0); splay(*y); return y; } static void expose_edge(node_type& node) { propagate(node); node_ptr ptr = &node; if (ptr->data.index() == 1) { splay(*ptr); ptr = ptr->p; } while (ptr) { splay(*ptr); node_type& v = *ptr->p; if (get_dir(v) != 1) { splay(*v.p); } if (get_dir(v) != 1) { splay(*v.p); } if (get_dir(v) == 2 && get_dir(*v.p) == 0) { splay(*v.p); } if (get_dir(v) == 0) { node_type& p = *v.p; p_replace(p, *ptr); link_child(v, &p, 1); link_child(p, p.c[2], 1); link_child(p, ptr->c[0], 0); link_child(p, ptr->c[2], 2); E e = std::move(std::get<solid_edge_node>(p.data).e); Point point = Info::to_point(e, get_sum_path(*p.c[1])); Point sum = Info::rake( point, Info::rake(get_sum_point(p.c[0]), get_sum_point(p.c[2]))); p.data = data_variant(std::in_place_type<dashed_edge_node>, std::move(e), std::move(point), std::move(sum)); } else { link_child(v, merge(ptr->c[0], ptr->c[2]), 1); p_replace(v, *ptr); } vertex_node& inner = std::get<vertex_node>(v.data); inner.path = Info::to_path(inner.v, get_sum_point(v.c[1])); link_child(*ptr, &v, 0); link_child(*ptr, ptr->c[1], 2); ptr->c[1] = nullptr; E e = std::move(std::get<dashed_edge_node>(ptr->data).e); Path sum = Info::compress(get_sum_path(*ptr->c[0]), e, get_sum_path(*ptr->c[2])); ptr->data = data_variant(std::in_place_type<solid_edge_node>, std::move(e), std::move(sum)); splay(*ptr); ptr = ptr->p; } splay(node); } static void check(const node_type& n) { if (n.p) { get_dir(n); } for (int i = 0; i < 3; i++) { if (n.c[i]) { assert(n.c[i]->p == &n); } } struct { const node_type& n; void operator()(const vertex_node&) const { assert(n.c[0] == nullptr); if (n.c[1]) { assert(n.c[1]->data.index() == 2); } assert(n.c[2] == nullptr); if (n.p) { assert(n.p->data.index() == 1 || n.p->data.index() == 2); } } void operator()(const solid_edge_node&) const { assert(n.c[0] != nullptr); assert(n.c[0]->data.index() == 0 || n.c[0]->data.index() == 1); assert(n.c[1] == nullptr); assert(n.c[2] != nullptr); assert(n.c[2]->data.index() == 0 || n.c[2]->data.index() == 1); if (n.p) { assert(n.p->data.index() == 1 || n.p->data.index() == 2); } } void operator()(const dashed_edge_node&) const { if (n.c[0]) { assert(n.c[0]->data.index() == 2); } assert(n.c[1] != nullptr); assert(n.c[1]->data.index() == 0 || n.c[1]->data.index() == 1); if (n.c[2]) { assert(n.c[2]->data.index() == 2); } assert(n.p != nullptr); assert(n.p->data.index() == 0 || n.p->data.index() == 2); } } visitor{ n }; std::visit(visitor, n.data); } static void check_cp(node_type& n) { struct { node_type& n; void operator()(vertex_node&) const { check_ds(n.c[1]); } void operator()(solid_edge_node&) const { check_cp(*n.c[0]); check_cp(*n.c[2]); } void operator()(dashed_edge_node&) const { assert(false); } } visitor{ n }; std::visit(visitor, n.data); } static void check_ds(const node_ptr ptr) { if (ptr) { struct { node_type& n; void operator()(vertex_node&) const { assert(false); } void operator()(solid_edge_node&) const { assert(false); } void operator()(dashed_edge_node&) const { check_ds(n.c[0]); check_cp(*n.c[1]); check_ds(n.c[2]); } } visitor{ *ptr }; std::visit(visitor, ptr->data); } } std::vector<node_type> vertex_nodes; std::vector<node_type> edge_nodes; node_ptr free_list; template <class... Args> node_type& allocate(Args &&... args) { if (free_list) { node_type& n = *free_list; free_list = n.c[0]; n = node_type(std::forward<Args>(args)...); return n; } else { edge_nodes.emplace_back(std::forward<Args>(args)...); return edge_nodes.back(); } } node_type& expose_vertex(const int v_) { node_type& v = vertex_nodes[v_]; if (v.p) { expose_edge(*v.p); } if (get_dir(v) == 2) { splay(*v.p); } if (get_dir(v) == 0) { node_type& p = *v.p; splay(p); p_replace(p, *p.c[0]); link_child(p, v.c[1], 0); link_child(p, p.c[2], 1); p.c[2] = nullptr; link_child(v, &p, 1); E e = std::move(std::get<solid_edge_node>(p.data).e); Point point = Info::to_point(e, get_sum_path(*p.c[1])); Point sum = Info::rake( point, Info::rake(get_sum_point(p.c[0]), get_sum_point(p.c[2]))); p.data = data_variant(std::in_place_type<dashed_edge_node>, std::move(e), std::move(point), std::move(sum)); vertex_node& inner = std::get<vertex_node>(v.data); inner.path = Info::to_path(inner.v, get_sum_point(v.c[1])); } if (v.p) { node_type& p = *v.p; splay(p); return p; } else { return v; } } node_type& evert(const int v) { node_type& r = expose_vertex(v); reverse(r); return r; } public: class edge_handle { friend top_tree; node_ptr ptr; edge_handle(const node_ptr ptr_) : ptr(ptr_) {} public: edge_handle() : ptr(nullptr) {} E get() const { struct { E operator()(vertex_node&) const { throw "top_tree: internal error"; } E operator()(solid_edge_node& n) const { return n.e; } E operator()(dashed_edge_node& n) const { return n.e; } } visitor{}; return std::visit(visitor, *ptr); } }; top_tree(std::vector<V> vertices) : vertex_nodes(), edge_nodes(), free_list(nullptr) { const int n = vertices.size(); vertex_nodes.reserve(n); for (int i = 0; i < n; i++) { Path sum = Info::to_path(vertices[i], Info::id()); vertex_nodes.emplace_back(std::in_place_type<vertex_node>, std::move(vertices[i]), std::move(sum)); } edge_nodes.reserve(n - 1); } void set_vertex(const int i, V v) { node_type& n = vertex_nodes[i]; vertex_node& inner = std::get<vertex_node>(n.data); inner.v = std::move(v); inner.path = Info::to_path(inner.v, get_sum_point(n.c[1])); // check(); if (n.p) { expose_edge(*n.p); } // check(); } void set_edge(const edge_handle h, E e) { expose_edge(*h.ptr); std::get<solid_edge_node>(h.ptr->data).e = std::move(e); update(*h.ptr); } Path get_path(const int u, const int v) { evert(u); // check(); node_type& r = expose_vertex(v); // check(); return get_sum_path(r); } edge_handle link(const int u, const int v, E e) { node_type& u_ = expose_vertex(u); node_type& v_ = evert(v); Path sum = Info::compress(get_sum_path(u_), e, get_sum_path(v_)); node_type& r = allocate(std::in_place_type<solid_edge_node>, std::move(e), std::move(sum)); link_child(r, &u_, 0); link_child(r, &v_, 2); return edge_handle(&r); } void cut(const edge_handle h) { node_type& n = *h.ptr; expose_edge(n); n.c[0]->p = nullptr; n.c[2]->p = nullptr; n.c[0] = free_list; free_list = &n; } void check() { for (auto& v : vertex_nodes) { check(v); } std::vector<bool> used(edge_nodes.size(), true); { node_ptr p = free_list; while (p) { used[p - edge_nodes.data()] = false; p = p->c[0]; } } for (int i = 0; i < edge_nodes.size(); i++) { if (used[i]) { check(edge_nodes[i]); } } for (auto& v : vertex_nodes) { if (!v.p) { check_cp(v); } } for (int i = 0; i < edge_nodes.size(); i++) { if (used[i] && !edge_nodes[i].p) { check_cp(edge_nodes[i]); } } } }; #include <map> using u64 = unsigned long long; struct lcasum { struct V { int id; bool on; }; struct E {}; struct Point { u64 score; u64 hollow; int count; }; struct Path { u64 scl, scr; u64 a; int count; }; static Point rake(Point x, Point y) { return { x.score + y.score ,x.hollow + y.hollow + u64(x.count) * u64(y.count), x.count + y.count }; } static Point id() { return { 0, 0 }; } static Path to_path(V v, Point p) { if (v.on) { p.score += u64(v.id) * u64(p.count); p.count += 1; } p.score += p.hollow * u64(v.id); return { p.score, p.score, u64(p.count) * u64(v.id), p.count }; } static Path compress(Path l, E, Path r) { return { l.scl + r.scl + l.a * r.count, l.scr + r.scr + r.a * l.count, l.a + r.a, l.count + r.count }; } static Path reverse(Path p) { std::swap(p.scl, p.scr); return p; } static Point to_point(E, Path p) { return { p.scl, 0, p.count }; } }; #include <algorithm> #include <cassert> #include <climits> #include <cstdint> #include <utility> #include <vector> namespace noshi91 { namespace tree_utility_impl { int bsr(int x) { #if defined(__GNUC__) return 31 - __builtin_clz(x); #elif defined(_MSC_VER) unsigned long i; _BitScanReverse(&i, x); return i; #else static_assert(false, "not implemented"); return -1; #endif } using std::vector; class tree_utility { class node_type { public: int subtree_size; int depth; int in; int out; int ladder; node_type() : subtree_size(1), depth(), in(), out(), ladder() {} }; int n_; int root_; vector<node_type> nodes; vector<vector<int>> sparse_table; vector<vector<int>> jump_table; vector<int> ladder; void comparator_in(int& u, int& v) const { if (nodes[u].in > nodes[v].in) { std::swap(u, v); } } bool compare_by_depth(int u, int v) const { return nodes[u].depth < nodes[v].depth; } int min_by_depth(int u, int v) const { if (compare_by_depth(u, v)) { return u; } else { return v; } } int max_by_depth(int u, int v) const { if (compare_by_depth(u, v)) { return v; } else { return u; } } bool is_ancestor_of(int u, int v) const { return nodes[u].in <= nodes[v].in && nodes[v].in <= nodes[u].out; } int level_ancestor_0(int u, int d) const { d = nodes[u].depth - d; if (d == 0) { return u; } else { int p = bsr(d); d -= 1 << p; u = jump_table[p][u]; return ladder[nodes[u].ladder - d]; } } int lca_0_ordered(int u, int v) const { u = nodes[u].in; v = nodes[v].in + 1; int p = bsr(v - u); return min_by_depth(sparse_table[p][u], sparse_table[p][v - (1 << p)]); } int lca_0(int u, int v) const { comparator_in(u, v); return lca_0_ordered(u, v); } int distance_(int u, int v) const { int lca_ = lca_0(u, v); return nodes[u].depth + nodes[v].depth - 2 * nodes[lca_].depth; } int jump_(int u, int v, int d) const { if (d < 0) { return -1; } int lca_ = lca_0(u, v); if (nodes[u].depth - d >= nodes[lca_].depth) { return level_ancestor_0(u, nodes[u].depth - d); } else { int t = 2 * nodes[lca_].depth + d - nodes[u].depth; if (t <= nodes[v].depth) { return level_ancestor_0(v, t); } else { return -1; } } } int step_(int u, int v) const { if (is_ancestor_of(u, v)) { if (u == v) { return -1; } else { return level_ancestor_0(v, nodes[u].depth + 1); } } else { return jump_table[0][u]; } } int meet_(int u, int v, int w) const { comparator_in(u, v); comparator_in(v, w); comparator_in(u, v); return max_by_depth(lca_0_ordered(u, v), lca_0_ordered(v, w)); } public: explicit tree_utility(int n, const vector<std::pair<int, int>>& edges) : n_(n), root_(0), nodes(n), sparse_table(), jump_table(), ladder(2 * n) { assert(n > 0); vector<vector<int>> g(n); for (const auto& e : edges) { assert(0 <= e.first && e.first < n); assert(0 <= e.second && e.second < n); g[e.first].push_back(e.second); g[e.second].push_back(e.first); } vector<int> tour; tour.reserve(2 * n - 1); vector<int> pare(n, -1); { vector<int> height(n, 0); vector<int> used(n, 0); auto dfs = [&](auto& dfs, int v) -> void { used[v] = 1; nodes[v].in = tour.size(); tour.push_back(v); for (int& u : g[v]) { assert(!used[u]); g[u].erase(std::find(g[u].begin(), g[u].end(), v)); pare[u] = v; nodes[u].depth = nodes[v].depth + 1; dfs(dfs, u); nodes[v].subtree_size += nodes[u].subtree_size; if (height[v] <= height[u]) { height[v] = height[u] + 1; std::swap(g[v].front(), u); } tour.push_back(v); } nodes[v].out = tour.size(); }; nodes[0].depth = 0; dfs(dfs, 0); assert( std::all_of(used.begin(), used.end(), [](int x) { return x == 1; })); } { for (int w = 1; 2 * w < 2 * n; w *= 2) { int s = 2 * n - 2 * w; vector<int> next(s); for (int i = 0; i < s; ++i) { next[i] = min_by_depth(tour[i], tour[i + w]); } sparse_table.push_back(std::move(tour)); tour = std::move(next); } sparse_table.push_back(std::move(tour)); } { int times = bsr(n); for (int i = 0; i < times; ++i) { vector<int> next(n); for (int i = 0; i < n; ++i) { if (pare[i] == -1) { next[i] = -1; } else { next[i] = pare[pare[i]]; } } jump_table.push_back(std::move(pare)); pare = std::move(next); } jump_table.push_back(std::move(pare)); } { int pos = 0; vector<int> path; path.reserve(n); auto dfs = [&](auto& dfs, int v, int d) -> void { path.push_back(v); bool pushed = false; for (int u : g[v]) { if (pushed) { dfs(dfs, u, path.size()); } else { dfs(dfs, u, d); pushed = true; } } if (!pushed) { int p = path.size(); int s = std::max(0, d - (p - d)); std::copy(path.begin() + s, path.end(), ladder.begin() + pos); for (int i = d; i < p; ++i) { nodes[path[i]].ladder = pos + (d - s) + i; } pos += p - s; } path.pop_back(); }; dfs(dfs, 0, 0); } } int size() const { return n_; } int root() const { return root_; } void reroot(int new_root) { root_ = new_root; } int depth(int v) const { assert(0 <= v && v < n_); return distance_(root_, v); } int subtree_size(int v) const { if (is_ancestor_of(root_, v)) { if (root_ == v) { return n_; } else { return nodes[v].subtree_size; } } else { int c = level_ancestor_0(root_, nodes[v].depth + 1); return n_ - nodes[c].subtree_size; } } int level_ancestor(int v, int d) const { assert(0 <= v && v < n_); return jump_(root_, v, d); } int kth_ancestor(int v, int k) const { assert(0 <= v && v < n_); return jump_(v, root_, k); } int parent(int v) const { assert(0 <= v && v < n_); return step_(v, root_); } int lca(int u, int v) const { assert(0 <= u && u < n_); assert(0 <= v && v < n_); return meet_(root_, u, v); } int distance(int u, int v) const { assert(0 <= u && u < n_); assert(0 <= v && v < n_); return distance_(u, v); } int cut_size(int u, int v) const { assert(0 <= u && u < n_); assert(0 <= v && v < n_); if (jump_table[0][u] == v) { return nodes[u].subtree_size; } else if (jump_table[0][v] == u) { return n_ - nodes[v].subtree_size; } else { return -1; } } int jump(int u, int v, int d) const { assert(0 <= u && u < n_); assert(0 <= v && v < n_); return jump_(u, v, d); } int step(int u, int v) const { assert(0 <= u && u < n_); assert(0 <= v && v < n_); return step_(u, v); } int meet(int u, int v, int w) const { assert(0 <= u && u < n_); assert(0 <= v && v < n_); assert(0 <= w && w < n_); return meet_(u, v, w); } }; } // namespace tree_utility_impl using tree_utility_impl::tree_utility; } // namespace noshi91 #include <iostream> #include <utility> #include <vector> int main() { std::ios::sync_with_stdio(false); std::cin.tie(nullptr); int N, Q; std::cin >> N >> Q; std::vector<lcasum::V> vs(N); for (int i = 0; i < N; i++) { vs[i] = { i+1, false }; } top_tree<lcasum> tree(vs); std::map<std::pair<int, int>, typename top_tree<lcasum>::edge_handle> map; std::vector<std::pair<int, int>> es; for (int i = 0; i < N - 1; i++) { int a, b; std::cin >> a >> b; a -= 1; b -= 1; map[std::minmax(a, b)] = tree.link(a, b, {}); es.push_back({ a, b }); } const noshi91::tree_utility ut(N, es); for (int i = 0; i < Q; i++) { int u, r, v; std::cin >> u >> r >> v; u--; r--; v--; vs[u].on ^= 1; tree.set_vertex(u, vs[u]); if (r == v) { std::cout << tree.get_path(r, r).scl << "\n"; } else { int p = ut.step(v, r); //std::cerr << "## " << v << " " << p << " " << r << "\n"; auto& ref = map[std::minmax(v, p)]; tree.cut(ref); std::cout << tree.get_path(v, v).scl << "\n"; ref = tree.link(v, p, {}); } } return 0; }