結果
| 問題 |
No.2163 LCA Sum Query
|
| コンテスト | |
| ユーザー |
 noshi91
|
| 提出日時 | 2022-12-14 00:50:55 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
RE
|
| 実行時間 | - |
| コード長 | 24,101 bytes |
| コンパイル時間 | 1,914 ms |
| コンパイル使用メモリ | 127,772 KB |
| 最終ジャッジ日時 | 2025-02-09 11:16:49 |
|
ジャッジサーバーID （参考情報） |
judge5 / judge3 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 2 |
| other | AC * 12 RE * 28 |
ソースコード
#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;
}