link_cut_tree.hpp¶
Link-Cut Tree for a dynamic forest with point assignment and ordered path products; all operations take amortized O(log n) time.
Verified by dynamic_tree_vertex_add_path_sum, dynamic_tree_vertex_set_path_composite.
维护动态森林的连边、断边、换根及路径信息；题目在线改变树结构并查询路径时使用。
Implementation¶
#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 child[2] = {-1, -1};
int parent = -1;
int auxiliary_size = 1;
bool reversed = false;
value_type value;
value_type forward_product;
value_type backward_product;
explicit node(const value_type &initial)
: value(initial), forward_product(initial), backward_product(initial) {}
};
std::vector<node> nodes;
link_cut_tree() = default;
explicit link_cut_tree(const std::vector<value_type> &values) {
build(values);
}
/// @brief Reset to isolated vertices carrying the given values.
void build(const std::vector<value_type> &values) {
nodes.clear();
nodes.reserve(values.size());
splay_stack.clear();
splay_stack.reserve(values.size());
for (const value_type &value : values) {
nodes.emplace_back(value);
}
}
/// @brief Return the number of vertices.
int size() const { return int(nodes.size()); }
/// @brief Return whether two vertices are in the same represented tree.
bool connected(int first, int second) {
check_vertex(first);
check_vertex(second);
return first == second || find_root(first) == find_root(second);
}
/// @brief Add an edge between different trees; return false if it would
/// create a cycle.
bool link(int first, int second) {
check_vertex(first);
check_vertex(second);
if (connected(first, second)) {
return false;
}
make_root(first);
nodes[first].parent = second;
return true;
}
/// @brief Remove an existing edge; return false when the vertices are not
/// directly adjacent.
bool cut(int first, int second) {
check_vertex(first);
check_vertex(second);
make_root(first);
access(second);
if (nodes[second].child[0] != first || nodes[first].child[1] != -1) {
return false;
}
nodes[second].child[0] = -1;
nodes[first].parent = -1;
pull(second);
return true;
}
/// @brief Change one vertex value.
void set(int vertex, const value_type &value) {
check_vertex(vertex);
access(vertex);
nodes[vertex].value = value;
pull(vertex);
}
/// @brief Return one vertex value.
const value_type &get(int vertex) {
check_vertex(vertex);
access(vertex);
return nodes[vertex].value;
}
/// @brief Return the ordered monoid product on the path from first to
/// second; the vertices must be connected.
value_type path_product(int first, int second) {
check_vertex(first);
check_vertex(second);
assert(connected(first, second));
make_root(first);
access(second);
return nodes[second].forward_product;
}
/// @brief Return the number of vertices on a connected path.
int path_size(int first, int second) {
check_vertex(first);
check_vertex(second);
assert(connected(first, second));
make_root(first);
access(second);
return nodes[second].auxiliary_size;
}
private:
std::vector<int> splay_stack;
void check_vertex(int vertex) const {
assert(0 <= vertex && vertex < size());
}
bool is_auxiliary_root(int vertex) const {
int parent = nodes[vertex].parent;
return parent == -1 || (nodes[parent].child[0] != vertex &&
nodes[parent].child[1] != vertex);
}
int auxiliary_size(int vertex) const {
return vertex == -1 ? 0 : nodes[vertex].auxiliary_size;
}
value_type forward_product(int vertex) const {
return vertex == -1 ? Monoid::unit() : nodes[vertex].forward_product;
}
value_type backward_product(int vertex) const {
return vertex == -1 ? Monoid::unit() : nodes[vertex].backward_product;
}
void pull(int vertex) {
int left = nodes[vertex].child[0];
int right = nodes[vertex].child[1];
nodes[vertex].auxiliary_size =
1 + auxiliary_size(left) + auxiliary_size(right);
nodes[vertex].forward_product =
Monoid::op(Monoid::op(forward_product(left), nodes[vertex].value),
forward_product(right));
nodes[vertex].backward_product =
Monoid::op(Monoid::op(backward_product(right), nodes[vertex].value),
backward_product(left));
}
void apply_reverse(int vertex) {
if (vertex == -1) {
return;
}
std::swap(nodes[vertex].child[0], nodes[vertex].child[1]);
std::swap(nodes[vertex].forward_product,
nodes[vertex].backward_product);
nodes[vertex].reversed = !nodes[vertex].reversed;
}
void push(int vertex) {
if (!nodes[vertex].reversed) {
return;
}
apply_reverse(nodes[vertex].child[0]);
apply_reverse(nodes[vertex].child[1]);
nodes[vertex].reversed = false;
}
void rotate(int vertex) {
int parent = nodes[vertex].parent;
int grandparent = nodes[parent].parent;
int direction = nodes[parent].child[1] == vertex;
int middle = nodes[vertex].child[direction ^ 1];
if (!is_auxiliary_root(parent)) {
nodes[grandparent].child[nodes[grandparent].child[1] == parent] = vertex;
}
nodes[vertex].parent = grandparent;
nodes[vertex].child[direction ^ 1] = parent;
nodes[parent].parent = vertex;
nodes[parent].child[direction] = middle;
if (middle != -1) {
nodes[middle].parent = parent;
}
pull(parent);
pull(vertex);
}
void splay(int vertex) {
splay_stack.clear();
splay_stack.push_back(vertex);
for (int current = vertex; !is_auxiliary_root(current);) {
current = nodes[current].parent;
splay_stack.push_back(current);
}
for (auto iterator = splay_stack.rbegin(); iterator != splay_stack.rend();
++iterator) {
push(*iterator);
}
while (!is_auxiliary_root(vertex)) {
int parent = nodes[vertex].parent;
int grandparent = nodes[parent].parent;
if (!is_auxiliary_root(parent)) {
bool vertex_right = nodes[parent].child[1] == vertex;
bool parent_right = nodes[grandparent].child[1] == parent;
rotate(vertex_right == parent_right ? parent : vertex);
}
rotate(vertex);
}
}
int access(int vertex) {
int last = -1;
for (int current = vertex; current != -1;) {
splay(current);
int path_parent = nodes[current].parent;
nodes[current].child[1] = last;
if (last != -1) {
nodes[last].parent = current;
}
pull(current);
last = current;
current = path_parent;
}
splay(vertex);
return last;
}
void make_root(int vertex) {
access(vertex);
apply_reverse(vertex);
}
int find_root(int vertex) {
access(vertex);
push(vertex);
while (nodes[vertex].child[0] != -1) {
vertex = nodes[vertex].child[0];
push(vertex);
}
splay(vertex);
return vertex;
}
};
} // 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 child[2] = {-1, -1};
int parent = -1;
int auxiliary_size = 1;
bool reversed = false;
value_type value;
value_type forward_product;
value_type backward_product;
explicit node(const value_type &initial)
: value(initial), forward_product(initial), backward_product(initial) {}
};
std::vector<node> nodes;
link_cut_tree() = default;
explicit link_cut_tree(const std::vector<value_type> &values) {
build(values);
}
/// @brief Reset to isolated vertices carrying the given values.
void build(const std::vector<value_type> &values) {
nodes.clear();
nodes.reserve(values.size());
splay_stack.clear();
splay_stack.reserve(values.size());
for (const value_type &value : values) {
nodes.emplace_back(value);
}
}
/// @brief Return the number of vertices.
int size() const { return int(nodes.size()); }
/// @brief Return whether two vertices are in the same represented tree.
bool connected(int first, int second) {
check_vertex(first);
check_vertex(second);
return first == second || find_root(first) == find_root(second);
}
/// @brief Add an edge between different trees; return false if it would
/// create a cycle.
bool link(int first, int second) {
check_vertex(first);
check_vertex(second);
if (connected(first, second)) {
return false;
}
make_root(first);
nodes[first].parent = second;
return true;
}
/// @brief Remove an existing edge; return false when the vertices are not
/// directly adjacent.
bool cut(int first, int second) {
check_vertex(first);
check_vertex(second);
make_root(first);
access(second);
if (nodes[second].child[0] != first || nodes[first].child[1] != -1) {
return false;
}
nodes[second].child[0] = -1;
nodes[first].parent = -1;
pull(second);
return true;
}
/// @brief Change one vertex value.
void set(int vertex, const value_type &value) {
check_vertex(vertex);
access(vertex);
nodes[vertex].value = value;
pull(vertex);
}
/// @brief Return one vertex value.
const value_type &get(int vertex) {
check_vertex(vertex);
access(vertex);
return nodes[vertex].value;
}
/// @brief Return the ordered monoid product on the path from first to
/// second; the vertices must be connected.
value_type path_product(int first, int second) {
check_vertex(first);
check_vertex(second);
assert(connected(first, second));
make_root(first);
access(second);
return nodes[second].forward_product;
}
/// @brief Return the number of vertices on a connected path.
int path_size(int first, int second) {
check_vertex(first);
check_vertex(second);
assert(connected(first, second));
make_root(first);
access(second);
return nodes[second].auxiliary_size;
}
private:
std::vector<int> splay_stack;
void check_vertex(int vertex) const {
assert(0 <= vertex && vertex < size());
}
bool is_auxiliary_root(int vertex) const {
int parent = nodes[vertex].parent;
return parent == -1 || (nodes[parent].child[0] != vertex &&
nodes[parent].child[1] != vertex);
}
int auxiliary_size(int vertex) const {
return vertex == -1 ? 0 : nodes[vertex].auxiliary_size;
}
value_type forward_product(int vertex) const {
return vertex == -1 ? Monoid::unit() : nodes[vertex].forward_product;
}
value_type backward_product(int vertex) const {
return vertex == -1 ? Monoid::unit() : nodes[vertex].backward_product;
}
void pull(int vertex) {
int left = nodes[vertex].child[0];
int right = nodes[vertex].child[1];
nodes[vertex].auxiliary_size =
1 + auxiliary_size(left) + auxiliary_size(right);
nodes[vertex].forward_product =
Monoid::op(Monoid::op(forward_product(left), nodes[vertex].value),
forward_product(right));
nodes[vertex].backward_product =
Monoid::op(Monoid::op(backward_product(right), nodes[vertex].value),
backward_product(left));
}
void apply_reverse(int vertex) {
if (vertex == -1) {
return;
}
std::swap(nodes[vertex].child[0], nodes[vertex].child[1]);
std::swap(nodes[vertex].forward_product,
nodes[vertex].backward_product);
nodes[vertex].reversed = !nodes[vertex].reversed;
}
void push(int vertex) {
if (!nodes[vertex].reversed) {
return;
}
apply_reverse(nodes[vertex].child[0]);
apply_reverse(nodes[vertex].child[1]);
nodes[vertex].reversed = false;
}
void rotate(int vertex) {
int parent = nodes[vertex].parent;
int grandparent = nodes[parent].parent;
int direction = nodes[parent].child[1] == vertex;
int middle = nodes[vertex].child[direction ^ 1];
if (!is_auxiliary_root(parent)) {
nodes[grandparent].child[nodes[grandparent].child[1] == parent] = vertex;
}
nodes[vertex].parent = grandparent;
nodes[vertex].child[direction ^ 1] = parent;
nodes[parent].parent = vertex;
nodes[parent].child[direction] = middle;
if (middle != -1) {
nodes[middle].parent = parent;
}
pull(parent);
pull(vertex);
}
void splay(int vertex) {
splay_stack.clear();
splay_stack.push_back(vertex);
for (int current = vertex; !is_auxiliary_root(current);) {
current = nodes[current].parent;
splay_stack.push_back(current);
}
for (auto iterator = splay_stack.rbegin(); iterator != splay_stack.rend();
++iterator) {
push(*iterator);
}
while (!is_auxiliary_root(vertex)) {
int parent = nodes[vertex].parent;
int grandparent = nodes[parent].parent;
if (!is_auxiliary_root(parent)) {
bool vertex_right = nodes[parent].child[1] == vertex;
bool parent_right = nodes[grandparent].child[1] == parent;
rotate(vertex_right == parent_right ? parent : vertex);
}
rotate(vertex);
}
}
int access(int vertex) {
int last = -1;
for (int current = vertex; current != -1;) {
splay(current);
int path_parent = nodes[current].parent;
nodes[current].child[1] = last;
if (last != -1) {
nodes[last].parent = current;
}
pull(current);
last = current;
current = path_parent;
}
splay(vertex);
return last;
}
void make_root(int vertex) {
access(vertex);
apply_reverse(vertex);
}
int find_root(int vertex) {
access(vertex);
push(vertex);
while (nodes[vertex].child[0] != -1) {
vertex = nodes[vertex].child[0];
push(vertex);
}
splay(vertex);
return vertex;
}
};
} // namespace noya