test/yosupo-judge/dynamic_tree_vertex_add_path_sum/main.link_cut_tree.test.cpp
Depends on
Code
#define PROBLEM "https://judge.yosupo.jp/problem/dynamic_tree_vertex_add_path_sum"
#include <iostream>
#include "Mylib/AlgebraicStructure/Monoid/sum.cpp"
#include "Mylib/DataStructure/LinkCutTree/link_cut_tree.cpp"
#include "Mylib/IO/input_tuples.cpp"
#include "Mylib/IO/input_tuples_with_index.cpp"
namespace hl = haar_lib;
int main() {
std::cin.tie(0);
std::ios::sync_with_stdio(false);
int N, Q;
std::cin >> N >> Q;
hl::link_cut_tree<hl::sum_monoid<int64_t>> lct(N);
for (auto [i, a] : hl::input_tuples_with_index<int64_t>(N)) {
lct.set(i, a);
}
for (auto [u, v] : hl::input_tuples<int, int>(N - 1)) {
lct.link(u, v);
}
for (auto [type] : hl::input_tuples<int>(Q)) {
switch (type) {
case 0: {
int u, v, w, x;
std::cin >> u >> v >> w >> x;
lct.cut(u, v);
lct.link(w, x);
break;
}
case 1: {
int p, x;
std::cin >> p >> x;
lct.update(p, x);
break;
}
case 2: {
int u, v;
std::cin >> u >> v;
auto ans = lct.fold(u, v);
std::cout << ans << std::endl;
break;
}
}
}
return 0;
}
#line 1 "test/yosupo-judge/dynamic_tree_vertex_add_path_sum/main.link_cut_tree.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/dynamic_tree_vertex_add_path_sum"
#include <iostream>
#line 2 "Mylib/AlgebraicStructure/Monoid/sum.cpp"
namespace haar_lib {
template <typename T>
struct sum_monoid {
using value_type = T;
value_type operator()() const { return 0; }
value_type operator()(value_type a, value_type b) const { return a + b; }
};
} // namespace haar_lib
#line 2 "Mylib/DataStructure/LinkCutTree/link_cut_tree.cpp"
#include <vector>
namespace haar_lib {
template <typename Monoid>
struct link_cut_node {
using value_type = typename Monoid::value_type;
using node = link_cut_node;
const static Monoid M;
int subsize;
node *left, *right, *parent;
bool rev;
value_type value, result;
link_cut_node() : subsize(1),
left(nullptr),
right(nullptr),
parent(nullptr),
rev(false),
value(M()),
result(M()) {}
bool is_root() const {
return !parent or (parent->left != this and parent->right != this);
}
void update_node_status() {
subsize = 1;
result = value;
if (left) {
left->push_down();
subsize += left->subsize;
result = M(result, left->result);
}
if (right) {
right->push_down();
subsize += right->subsize;
result = M(result, right->result);
}
}
void push_down() {
if (rev) {
std::swap(left, right);
if (left) left->rev ^= true;
if (right) right->rev ^= true;
rev = false;
}
}
void rot(int dir_right) {
node *p = parent, *g = p->parent;
if (dir_right) {
if ((p->left = right)) right->parent = p;
right = p;
p->parent = this;
} else {
if ((p->right = left)) left->parent = p;
left = p;
p->parent = this;
}
p->update_node_status();
update_node_status();
parent = g;
if (not g) return;
if (g->left == p) g->left = this;
if (g->right == p) g->right = this;
g->update_node_status();
}
void splay() {
while (not is_root()) {
node *p = parent, *gp = p->parent;
if (p->is_root()) {
p->push_down();
push_down();
rot(this == p->left);
} else {
gp->push_down();
p->push_down();
push_down();
bool flag = this == p->left;
if ((this == p->left) == (p == gp->left)) {
p->rot(flag);
rot(flag);
} else {
rot(flag);
rot(not flag);
}
}
}
push_down();
}
static void expose(node *u) {
node *rp = nullptr;
for (node *p = u; p; p = p->parent) {
p->splay();
p->right = rp;
p->update_node_status();
rp = p;
}
u->splay();
}
static void link(node *u, node *v) {
evert(u);
u->parent = v;
}
static void cut(node *u) {
expose(u);
u->left->parent = nullptr;
u->left = nullptr;
u->update_node_status();
}
static void cut(node *u, node *v) {
expose(u);
expose(v);
if (u->is_root())
u->parent = nullptr;
else {
v->left->parent = nullptr;
v->left = nullptr;
v->update_node_status();
}
}
static void evert(node *u) {
expose(u);
u->rev ^= true;
u->push_down();
}
};
template <typename Monoid>
class link_cut_tree {
public:
using value_type = typename Monoid::value_type;
private:
using node = link_cut_node<Monoid>;
Monoid M_;
int N_;
std::vector<node *> nodes_;
public:
link_cut_tree() {}
link_cut_tree(int N) : N_(N), nodes_(N) {
for (int i = 0; i < N_; ++i) {
nodes_[i] = new node();
}
}
void expose(int k) {
node::expose(nodes_[k]);
}
void cut(int i, int j) {
node::cut(nodes_[i], nodes_[j]);
}
void link(int i, int j) {
node::link(nodes_[i], nodes_[j]);
}
void evert(int k) {
node::evert(nodes_[k]);
}
void set(int k, value_type x) {
node::evert(nodes_[k]);
nodes_[k]->value = x;
nodes_[k]->push_down();
}
void update(int k, value_type x) {
set(k, M_(get(k), x));
}
value_type get(int k) const {
return nodes_[k]->value;
}
value_type fold(int i, int j) {
node::evert(nodes_[i]);
node::expose(nodes_[j]);
return nodes_[j]->result;
}
};
} // namespace haar_lib
#line 2 "Mylib/IO/input_tuples.cpp"
#include <initializer_list>
#line 4 "Mylib/IO/input_tuples.cpp"
#include <tuple>
#include <utility>
#line 6 "Mylib/IO/input_tuple.cpp"
namespace haar_lib {
template <typename T, size_t... I>
static void input_tuple_helper(std::istream &s, T &val, std::index_sequence<I...>) {
(void) std::initializer_list<int>{(void(s >> std::get<I>(val)), 0)...};
}
template <typename T, typename U>
std::istream &operator>>(std::istream &s, std::pair<T, U> &value) {
s >> value.first >> value.second;
return s;
}
template <typename... Args>
std::istream &operator>>(std::istream &s, std::tuple<Args...> &value) {
input_tuple_helper(s, value, std::make_index_sequence<sizeof...(Args)>());
return s;
}
} // namespace haar_lib
#line 8 "Mylib/IO/input_tuples.cpp"
namespace haar_lib {
template <typename... Args>
class InputTuples {
struct iter {
using value_type = std::tuple<Args...>;
value_type value;
bool fetched = false;
int N, c = 0;
value_type operator*() {
if (not fetched) {
std::cin >> value;
}
return value;
}
void operator++() {
++c;
fetched = false;
}
bool operator!=(iter &) const {
return c < N;
}
iter(int N) : N(N) {}
};
int N;
public:
InputTuples(int N) : N(N) {}
iter begin() const { return iter(N); }
iter end() const { return iter(N); }
};
template <typename... Args>
auto input_tuples(int N) {
return InputTuples<Args...>(N);
}
} // namespace haar_lib
#line 8 "Mylib/IO/input_tuples_with_index.cpp"
namespace haar_lib {
template <typename... Args>
class InputTuplesWithIndex {
struct iter {
using value_type = std::tuple<int, Args...>;
value_type value;
bool fetched = false;
int N;
int c = 0;
value_type operator*() {
if (not fetched) {
std::tuple<Args...> temp;
std::cin >> temp;
value = std::tuple_cat(std::make_tuple(c), temp);
}
return value;
}
void operator++() {
++c;
fetched = false;
}
bool operator!=(iter &) const {
return c < N;
}
iter(int N) : N(N) {}
};
int N;
public:
InputTuplesWithIndex(int N) : N(N) {}
iter begin() const { return iter(N); }
iter end() const { return iter(N); }
};
template <typename... Args>
auto input_tuples_with_index(int N) {
return InputTuplesWithIndex<Args...>(N);
}
} // namespace haar_lib
#line 8 "test/yosupo-judge/dynamic_tree_vertex_add_path_sum/main.link_cut_tree.test.cpp"
namespace hl = haar_lib;
int main() {
std::cin.tie(0);
std::ios::sync_with_stdio(false);
int N, Q;
std::cin >> N >> Q;
hl::link_cut_tree<hl::sum_monoid<int64_t>> lct(N);
for (auto [i, a] : hl::input_tuples_with_index<int64_t>(N)) {
lct.set(i, a);
}
for (auto [u, v] : hl::input_tuples<int, int>(N - 1)) {
lct.link(u, v);
}
for (auto [type] : hl::input_tuples<int>(Q)) {
switch (type) {
case 0: {
int u, v, w, x;
std::cin >> u >> v >> w >> x;
lct.cut(u, v);
lct.link(w, x);
break;
}
case 1: {
int p, x;
std::cin >> p >> x;
lct.update(p, x);
break;
}
case 2: {
int u, v;
std::cin >> u >> v;
auto ans = lct.fold(u, v);
std::cout << ans << std::endl;
break;
}
}
}
return 0;
}
Back to top page
Sum monoid
(Mylib/AlgebraicStructure/Monoid/sum.cpp)