link_cut_tree.hpp¶
维护动态森林的连边、断边、换根及路径信息；题目在线改变树结构并查询路径时使用。
Complexity: Time: Amortized O(log n) per dynamic-tree operation. Space: O(n).
AC 记录：dynamic_tree_vertex_add_path_sum, dynamic_tree_vertex_set_path_composite。
Implementation¶
当前头文件，省略 include guard；依赖见 #include。
/// @complexity Time: Amortized O(log n) per dynamic-tree operation.
/// Space: O(n).
#include <algorithm>
#include <cassert>
#include <utility>
#include <vector>
namespace noya {
/// @brief Link-Cut Tree for a dynamic forest with point assignment and ordered
/// path products; all operations take amortized O(log n) time.
template <class Monoid> struct link_cut_tree {
using value_type = typename Monoid::value_type;
struct node {
int ch[2] = {-1, -1};
int fa = -1;
int sz = 1;
bool rev = false;
value_type val;
value_type fwd;
value_type bwd;
explicit node(const value_type &a0) : val(a0), fwd(a0), bwd(a0) {}
};
std::vector<node> tr;
link_cut_tree() = default;
explicit link_cut_tree(const std::vector<value_type> &a) { build(a); }
/// @brief Reset to isolated vertices carrying the given values.
void build(const std::vector<value_type> &a) {
tr.clear();
tr.reserve(a.size());
st.clear();
st.reserve(a.size());
for (const value_type &val : a) {
tr.emplace_back(val);
}
}
/// @brief Return the number of vertices.
int size() const { return int(tr.size()); }
/// @brief Return whether two vertices are in the same represented tree.
bool connected(int arr, int b) {
check_vertex(arr);
check_vertex(b);
return arr == b || find_root(arr) == find_root(b);
}
/// @brief Add an edge between different trees; return false if it would
/// create a cycle.
bool link(int arr, int b) {
check_vertex(arr);
check_vertex(b);
if (connected(arr, b)) {
return false;
}
make_root(arr);
tr[arr].fa = b;
return true;
}
/// @brief Remove an existing edge; return false when the vertices are not
/// directly adjacent.
bool cut(int arr, int b) {
check_vertex(arr);
check_vertex(b);
make_root(arr);
access(b);
if (tr[b].ch[0] != arr || tr[arr].ch[1] != -1) {
return false;
}
tr[b].ch[0] = -1;
tr[arr].fa = -1;
pull(b);
return true;
}
/// @brief Change one vertex value.
void set(int u, const value_type &val) {
check_vertex(u);
access(u);
tr[u].val = val;
pull(u);
}
/// @brief Return one vertex value.
const value_type &get(int u) {
check_vertex(u);
access(u);
return tr[u].val;
}
/// @brief Return the ordered monoid product on the path from first to
/// second; the vertices must be connected.
value_type path_product(int arr, int b) {
check_vertex(arr);
check_vertex(b);
assert(connected(arr, b));
make_root(arr);
access(b);
return tr[b].fwd;
}
/// @brief Return the number of vertices on a connected path.
int path_size(int arr, int b) {
check_vertex(arr);
check_vertex(b);
assert(connected(arr, b));
make_root(arr);
access(b);
return tr[b].sz;
}
private:
std::vector<int> st;
void check_vertex(int u) const { assert(0 <= u && u < size()); }
bool is_auxiliary_root(int u) const {
int fa = tr[u].fa;
return fa == -1 || (tr[fa].ch[0] != u && tr[fa].ch[1] != u);
}
int auxiliary_size(int u) const { return u == -1 ? 0 : tr[u].sz; }
value_type forward_product(int u) const {
return u == -1 ? Monoid::unit() : tr[u].fwd;
}
value_type backward_product(int u) const {
return u == -1 ? Monoid::unit() : tr[u].bwd;
}
void pull(int u) {
int l = tr[u].ch[0];
int r = tr[u].ch[1];
tr[u].sz = 1 + auxiliary_size(l) + auxiliary_size(r);
tr[u].fwd = Monoid::op(Monoid::op(forward_product(l), tr[u].val),
forward_product(r));
tr[u].bwd = Monoid::op(Monoid::op(backward_product(r), tr[u].val),
backward_product(l));
}
void apply_reverse(int u) {
if (u == -1) {
return;
}
std::swap(tr[u].ch[0], tr[u].ch[1]);
std::swap(tr[u].fwd, tr[u].bwd);
tr[u].rev = !tr[u].rev;
}
void push(int u) {
if (!tr[u].rev) {
return;
}
apply_reverse(tr[u].ch[0]);
apply_reverse(tr[u].ch[1]);
tr[u].rev = false;
}
void rotate(int u) {
int fa = tr[u].fa;
int gp = tr[fa].fa;
int dir = tr[fa].ch[1] == u;
int mid = tr[u].ch[dir ^ 1];
if (!is_auxiliary_root(fa)) {
tr[gp].ch[tr[gp].ch[1] == fa] = u;
}
tr[u].fa = gp;
tr[u].ch[dir ^ 1] = fa;
tr[fa].fa = u;
tr[fa].ch[dir] = mid;
if (mid != -1) {
tr[mid].fa = fa;
}
pull(fa);
pull(u);
}
void splay(int u) {
st.clear();
st.push_back(u);
for (int cur = u; !is_auxiliary_root(cur);) {
cur = tr[cur].fa;
st.push_back(cur);
}
for (auto it = st.rbegin(); it != st.rend(); ++it) {
push(*it);
}
while (!is_auxiliary_root(u)) {
int fa = tr[u].fa;
int gp = tr[fa].fa;
if (!is_auxiliary_root(fa)) {
bool dx = tr[fa].ch[1] == u;
bool dp = tr[gp].ch[1] == fa;
rotate(dx == dp ? fa : u);
}
rotate(u);
}
}
int access(int u) {
int lst = -1;
for (int cur = u; cur != -1;) {
splay(cur);
int pp = tr[cur].fa;
tr[cur].ch[1] = lst;
if (lst != -1) {
tr[lst].fa = cur;
}
pull(cur);
lst = cur;
cur = pp;
}
splay(u);
return lst;
}
void make_root(int u) {
access(u);
apply_reverse(u);
}
int find_root(int u) {
access(u);
push(u);
while (tr[u].ch[0] != -1) {
u = tr[u].ch[0];
push(u);
}
splay(u);
return u;
}
};
} // namespace noya
#ifndef NOYA_LINK_CUT_TREE_HPP
#define NOYA_LINK_CUT_TREE_HPP 1
/// @complexity Time: Amortized O(log n) per dynamic-tree operation.
/// Space: O(n).
#include <algorithm>
#include <cassert>
#include <utility>
#include <vector>
namespace noya {
/// @brief Link-Cut Tree for a dynamic forest with point assignment and ordered
/// path products; all operations take amortized O(log n) time.
template <class Monoid> struct link_cut_tree {
using value_type = typename Monoid::value_type;
struct node {
int ch[2] = {-1, -1};
int fa = -1;
int sz = 1;
bool rev = false;
value_type val;
value_type fwd;
value_type bwd;
explicit node(const value_type &a0) : val(a0), fwd(a0), bwd(a0) {}
};
std::vector<node> tr;
link_cut_tree() = default;
explicit link_cut_tree(const std::vector<value_type> &a) { build(a); }
/// @brief Reset to isolated vertices carrying the given values.
void build(const std::vector<value_type> &a) {
tr.clear();
tr.reserve(a.size());
st.clear();
st.reserve(a.size());
for (const value_type &val : a) {
tr.emplace_back(val);
}
}
/// @brief Return the number of vertices.
int size() const { return int(tr.size()); }
/// @brief Return whether two vertices are in the same represented tree.
bool connected(int arr, int b) {
check_vertex(arr);
check_vertex(b);
return arr == b || find_root(arr) == find_root(b);
}
/// @brief Add an edge between different trees; return false if it would
/// create a cycle.
bool link(int arr, int b) {
check_vertex(arr);
check_vertex(b);
if (connected(arr, b)) {
return false;
}
make_root(arr);
tr[arr].fa = b;
return true;
}
/// @brief Remove an existing edge; return false when the vertices are not
/// directly adjacent.
bool cut(int arr, int b) {
check_vertex(arr);
check_vertex(b);
make_root(arr);
access(b);
if (tr[b].ch[0] != arr || tr[arr].ch[1] != -1) {
return false;
}
tr[b].ch[0] = -1;
tr[arr].fa = -1;
pull(b);
return true;
}
/// @brief Change one vertex value.
void set(int u, const value_type &val) {
check_vertex(u);
access(u);
tr[u].val = val;
pull(u);
}
/// @brief Return one vertex value.
const value_type &get(int u) {
check_vertex(u);
access(u);
return tr[u].val;
}
/// @brief Return the ordered monoid product on the path from first to
/// second; the vertices must be connected.
value_type path_product(int arr, int b) {
check_vertex(arr);
check_vertex(b);
assert(connected(arr, b));
make_root(arr);
access(b);
return tr[b].fwd;
}
/// @brief Return the number of vertices on a connected path.
int path_size(int arr, int b) {
check_vertex(arr);
check_vertex(b);
assert(connected(arr, b));
make_root(arr);
access(b);
return tr[b].sz;
}
private:
std::vector<int> st;
void check_vertex(int u) const { assert(0 <= u && u < size()); }
bool is_auxiliary_root(int u) const {
int fa = tr[u].fa;
return fa == -1 || (tr[fa].ch[0] != u && tr[fa].ch[1] != u);
}
int auxiliary_size(int u) const { return u == -1 ? 0 : tr[u].sz; }
value_type forward_product(int u) const {
return u == -1 ? Monoid::unit() : tr[u].fwd;
}
value_type backward_product(int u) const {
return u == -1 ? Monoid::unit() : tr[u].bwd;
}
void pull(int u) {
int l = tr[u].ch[0];
int r = tr[u].ch[1];
tr[u].sz = 1 + auxiliary_size(l) + auxiliary_size(r);
tr[u].fwd = Monoid::op(Monoid::op(forward_product(l), tr[u].val),
forward_product(r));
tr[u].bwd = Monoid::op(Monoid::op(backward_product(r), tr[u].val),
backward_product(l));
}
void apply_reverse(int u) {
if (u == -1) {
return;
}
std::swap(tr[u].ch[0], tr[u].ch[1]);
std::swap(tr[u].fwd, tr[u].bwd);
tr[u].rev = !tr[u].rev;
}
void push(int u) {
if (!tr[u].rev) {
return;
}
apply_reverse(tr[u].ch[0]);
apply_reverse(tr[u].ch[1]);
tr[u].rev = false;
}
void rotate(int u) {
int fa = tr[u].fa;
int gp = tr[fa].fa;
int dir = tr[fa].ch[1] == u;
int mid = tr[u].ch[dir ^ 1];
if (!is_auxiliary_root(fa)) {
tr[gp].ch[tr[gp].ch[1] == fa] = u;
}
tr[u].fa = gp;
tr[u].ch[dir ^ 1] = fa;
tr[fa].fa = u;
tr[fa].ch[dir] = mid;
if (mid != -1) {
tr[mid].fa = fa;
}
pull(fa);
pull(u);
}
void splay(int u) {
st.clear();
st.push_back(u);
for (int cur = u; !is_auxiliary_root(cur);) {
cur = tr[cur].fa;
st.push_back(cur);
}
for (auto it = st.rbegin(); it != st.rend(); ++it) {
push(*it);
}
while (!is_auxiliary_root(u)) {
int fa = tr[u].fa;
int gp = tr[fa].fa;
if (!is_auxiliary_root(fa)) {
bool dx = tr[fa].ch[1] == u;
bool dp = tr[gp].ch[1] == fa;
rotate(dx == dp ? fa : u);
}
rotate(u);
}
}
int access(int u) {
int lst = -1;
for (int cur = u; cur != -1;) {
splay(cur);
int pp = tr[cur].fa;
tr[cur].ch[1] = lst;
if (lst != -1) {
tr[lst].fa = cur;
}
pull(cur);
lst = cur;
cur = pp;
}
splay(u);
return lst;
}
void make_root(int u) {
access(u);
apply_reverse(u);
}
int find_root(int u) {
access(u);
push(u);
while (tr[u].ch[0] != -1) {
u = tr[u].ch[0];
push(u);
}
splay(u);
return u;
}
};
} // namespace noya
#endif // NOYA_LINK_CUT_TREE_HPP
#include <algorithm>
#include <cassert>
#include <utility>
#include <vector>
/// @complexity Time: Amortized O(log n) per dynamic-tree operation.
/// Space: O(n).
namespace noya {
/// @brief Link-Cut Tree for a dynamic forest with point assignment and ordered
/// path products; all operations take amortized O(log n) time.
template <class Monoid> struct link_cut_tree {
using value_type = typename Monoid::value_type;
struct node {
int ch[2] = {-1, -1};
int fa = -1;
int sz = 1;
bool rev = false;
value_type val;
value_type fwd;
value_type bwd;
explicit node(const value_type &a0) : val(a0), fwd(a0), bwd(a0) {}
};
std::vector<node> tr;
link_cut_tree() = default;
explicit link_cut_tree(const std::vector<value_type> &a) { build(a); }
/// @brief Reset to isolated vertices carrying the given values.
void build(const std::vector<value_type> &a) {
tr.clear();
tr.reserve(a.size());
st.clear();
st.reserve(a.size());
for (const value_type &val : a) {
tr.emplace_back(val);
}
}
/// @brief Return the number of vertices.
int size() const { return int(tr.size()); }
/// @brief Return whether two vertices are in the same represented tree.
bool connected(int arr, int b) {
check_vertex(arr);
check_vertex(b);
return arr == b || find_root(arr) == find_root(b);
}
/// @brief Add an edge between different trees; return false if it would
/// create a cycle.
bool link(int arr, int b) {
check_vertex(arr);
check_vertex(b);
if (connected(arr, b)) {
return false;
}
make_root(arr);
tr[arr].fa = b;
return true;
}
/// @brief Remove an existing edge; return false when the vertices are not
/// directly adjacent.
bool cut(int arr, int b) {
check_vertex(arr);
check_vertex(b);
make_root(arr);
access(b);
if (tr[b].ch[0] != arr || tr[arr].ch[1] != -1) {
return false;
}
tr[b].ch[0] = -1;
tr[arr].fa = -1;
pull(b);
return true;
}
/// @brief Change one vertex value.
void set(int u, const value_type &val) {
check_vertex(u);
access(u);
tr[u].val = val;
pull(u);
}
/// @brief Return one vertex value.
const value_type &get(int u) {
check_vertex(u);
access(u);
return tr[u].val;
}
/// @brief Return the ordered monoid product on the path from first to
/// second; the vertices must be connected.
value_type path_product(int arr, int b) {
check_vertex(arr);
check_vertex(b);
assert(connected(arr, b));
make_root(arr);
access(b);
return tr[b].fwd;
}
/// @brief Return the number of vertices on a connected path.
int path_size(int arr, int b) {
check_vertex(arr);
check_vertex(b);
assert(connected(arr, b));
make_root(arr);
access(b);
return tr[b].sz;
}
private:
std::vector<int> st;
void check_vertex(int u) const { assert(0 <= u && u < size()); }
bool is_auxiliary_root(int u) const {
int fa = tr[u].fa;
return fa == -1 || (tr[fa].ch[0] != u && tr[fa].ch[1] != u);
}
int auxiliary_size(int u) const { return u == -1 ? 0 : tr[u].sz; }
value_type forward_product(int u) const {
return u == -1 ? Monoid::unit() : tr[u].fwd;
}
value_type backward_product(int u) const {
return u == -1 ? Monoid::unit() : tr[u].bwd;
}
void pull(int u) {
int l = tr[u].ch[0];
int r = tr[u].ch[1];
tr[u].sz = 1 + auxiliary_size(l) + auxiliary_size(r);
tr[u].fwd = Monoid::op(Monoid::op(forward_product(l), tr[u].val),
forward_product(r));
tr[u].bwd = Monoid::op(Monoid::op(backward_product(r), tr[u].val),
backward_product(l));
}
void apply_reverse(int u) {
if (u == -1) {
return;
}
std::swap(tr[u].ch[0], tr[u].ch[1]);
std::swap(tr[u].fwd, tr[u].bwd);
tr[u].rev = !tr[u].rev;
}
void push(int u) {
if (!tr[u].rev) {
return;
}
apply_reverse(tr[u].ch[0]);
apply_reverse(tr[u].ch[1]);
tr[u].rev = false;
}
void rotate(int u) {
int fa = tr[u].fa;
int gp = tr[fa].fa;
int dir = tr[fa].ch[1] == u;
int mid = tr[u].ch[dir ^ 1];
if (!is_auxiliary_root(fa)) {
tr[gp].ch[tr[gp].ch[1] == fa] = u;
}
tr[u].fa = gp;
tr[u].ch[dir ^ 1] = fa;
tr[fa].fa = u;
tr[fa].ch[dir] = mid;
if (mid != -1) {
tr[mid].fa = fa;
}
pull(fa);
pull(u);
}
void splay(int u) {
st.clear();
st.push_back(u);
for (int cur = u; !is_auxiliary_root(cur);) {
cur = tr[cur].fa;
st.push_back(cur);
}
for (auto it = st.rbegin(); it != st.rend(); ++it) {
push(*it);
}
while (!is_auxiliary_root(u)) {
int fa = tr[u].fa;
int gp = tr[fa].fa;
if (!is_auxiliary_root(fa)) {
bool dx = tr[fa].ch[1] == u;
bool dp = tr[gp].ch[1] == fa;
rotate(dx == dp ? fa : u);
}
rotate(u);
}
}
int access(int u) {
int lst = -1;
for (int cur = u; cur != -1;) {
splay(cur);
int pp = tr[cur].fa;
tr[cur].ch[1] = lst;
if (lst != -1) {
tr[lst].fa = cur;
}
pull(cur);
lst = cur;
cur = pp;
}
splay(u);
return lst;
}
void make_root(int u) {
access(u);
apply_reverse(u);
}
int find_root(int u) {
access(u);
push(u);
while (tr[u].ch[0] != -1) {
u = tr[u].ch[0];
push(u);
}
splay(u);
return u;
}
};
} // namespace noya