dynamic_rerooting_top_tree.hpp¶
用 Top Tree 维护动态森林的换根及子树 DP，支持连边、断边和单点赋值。
Complexity: Time: \(O(\log n)\) amortized per link, cut, point update, reroot, or aggregate query, for \(O(1)\) DP operations. Releasing the last owner is \(O(n)\). Space: \(O(n)\), including recycled nodes.
Source: Nyaan
Implementation¶
当前头文件，省略 include guard；依赖见 #include。
/// @complexity Time: O(log n) amortized per link, cut, point update, reroot,
/// or aggregate query, for O(1) DP operations. Releasing the last owner is O(n).
/// Space: O(n), including recycled nodes.
#include <algorithm>
#include <cassert>
#include <cstddef>
#include <deque>
#include <limits>
#include <memory>
#include <utility>
#include <vector>
namespace noya {
namespace dynamic_rerooting_internal {
template <class Point, auto rk> class dashed_splay_tree {
public:
struct node {
node *l = nullptr;
node *r = nullptr;
node *fa = nullptr;
Point key;
Point sum;
explicit node(const Point &val) : key(val), sum(val) {}
};
using node_pointer = node *;
private:
std::deque<node> nodes;
std::vector<node_pointer> free;
node_pointer allocate(const Point &val) {
if (free.empty()) {
nodes.emplace_back(val);
return &nodes.back();
}
node_pointer cur = free.back();
free.pop_back();
cur->l = cur->r = cur->fa = nullptr;
cur->key = cur->sum = val;
return cur;
}
static void update(node_pointer cur) {
cur->sum = cur->key;
if (cur->l) {
cur->sum = rk(cur->sum, cur->l->sum);
}
if (cur->r) {
cur->sum = rk(cur->sum, cur->r->sum);
}
}
static void rotate_right(node_pointer cur) {
node_pointer fa = cur->fa;
node_pointer gf = fa->fa;
fa->l = cur->r;
if (cur->r) {
cur->r->fa = fa;
}
cur->r = fa;
fa->fa = cur;
update(fa);
cur->fa = gf;
if (gf) {
if (gf->l == fa) {
gf->l = cur;
}
if (gf->r == fa) {
gf->r = cur;
}
}
}
static void rotate_left(node_pointer cur) {
node_pointer fa = cur->fa;
node_pointer gf = fa->fa;
fa->r = cur->l;
if (cur->l) {
cur->l->fa = fa;
}
cur->l = fa;
fa->fa = cur;
update(fa);
cur->fa = gf;
if (gf) {
if (gf->l == fa) {
gf->l = cur;
}
if (gf->r == fa) {
gf->r = cur;
}
}
}
static node_pointer rightmost(node_pointer cur) {
while (cur->r) {
cur = cur->r;
}
return cur;
}
public:
static void splay(node_pointer cur) {
if (!cur->fa) {
return;
}
while (cur->fa) {
node_pointer fa = cur->fa;
if (!fa->fa) {
if (fa->l == cur) {
rotate_right(cur);
} else {
rotate_left(cur);
}
} else {
node_pointer gf = fa->fa;
if (gf->l == fa) {
if (fa->l == cur) {
rotate_right(fa);
rotate_right(cur);
} else {
rotate_left(cur);
rotate_right(cur);
}
} else if (fa->r == cur) {
rotate_left(fa);
rotate_left(cur);
} else {
rotate_right(cur);
rotate_left(cur);
}
}
}
update(cur);
}
node_pointer insert(node_pointer rt, const Point &val) {
node_pointer ins = allocate(val);
// Rake is commutative: the previous tree can become the new root's left
// child directly, without searching for and splaying its rightmost node.
ins->l = rt;
if (rt) {
rt->fa = ins;
update(ins);
}
return ins;
}
node_pointer erase(node_pointer cur) {
splay(cur);
node_pointer l = cur->l;
node_pointer r = cur->r;
free.push_back(cur);
if (!l) {
if (r) {
r->fa = nullptr;
}
return r;
}
if (!r) {
l->fa = nullptr;
return l;
}
l->fa = nullptr;
node_pointer rt = rightmost(l);
splay(rt);
rt->r = r;
r->fa = rt;
update(rt);
return rt;
}
};
} // namespace dynamic_rerooting_internal
/// @brief Dynamic rerooting DP on a top tree represented by preferred paths.
/// `cmp` joins consecutive path clusters, while commutative `rk`
/// combines light subtrees. `ae` changes a path cluster into a point
/// cluster and `av` attaches all light clusters to one path vertex.
/// Expose moves preferred edges between the path splay and the dashed-edge
/// splay, so both forward and reversed path aggregates stay current.
/// DP operations must obey the path/rake composition laws and be pure.
/// Copies share the same forest. Stable node handles are owned by that shared
/// storage; do not delete them or use them after the last owner is released.
/// Link different components with v as a represented root; cut a nonroot.
template <class Path, class Point, class Info, auto vtx, auto cmp, auto rk,
auto ae, auto av>
class dynamic_rerooting_top_tree {
using dashed_tree = dynamic_rerooting_internal::dashed_splay_tree<Point, rk>;
struct node {
node *l = nullptr;
node *r = nullptr;
node *fa = nullptr;
Info inf;
Path key{};
Path fwd{};
Path bwd{};
typename dashed_tree::node_pointer lt = nullptr;
typename dashed_tree::node_pointer lp = nullptr;
bool rev = false;
explicit node(const Info &val) : inf(val) {}
bool is_auxiliary_root() const {
return !fa || (fa->l != this && fa->r != this);
}
};
struct storage {
std::deque<node> vertices;
dashed_tree dashed;
};
std::shared_ptr<storage> owner = std::make_shared<storage>();
public:
using node_pointer = node *;
private:
static void toggle(node_pointer cur) {
std::swap(cur->l, cur->r);
std::swap(cur->fwd, cur->bwd);
cur->rev ^= true;
}
static void push(node_pointer cur) {
if (!cur->rev) {
return;
}
if (cur->l) {
toggle(cur->l);
}
if (cur->r) {
toggle(cur->r);
}
cur->rev = false;
}
static void pull(node_pointer cur) {
Path fwd = cur->key;
Path bwd = cur->key;
if (cur->l) {
fwd = cmp(cur->l->fwd, fwd);
bwd = cmp(bwd, cur->l->bwd);
}
if (cur->r) {
fwd = cmp(fwd, cur->r->fwd);
bwd = cmp(cur->r->bwd, bwd);
}
cur->fwd = fwd;
cur->bwd = bwd;
}
static void update(node_pointer cur) {
cur->key = cur->lt ? av(cur->lt->sum, cur->inf) : vtx(cur->inf);
pull(cur);
}
static void rotate_right(node_pointer cur) {
node_pointer fa = cur->fa;
node_pointer gf = fa->fa;
if (fa->is_auxiliary_root()) {
cur->lp = fa->lp;
fa->lp = nullptr;
}
push(fa);
push(cur);
fa->l = cur->r;
if (cur->r) {
cur->r->fa = fa;
}
cur->r = fa;
fa->fa = cur;
pull(fa);
cur->fa = gf;
if (gf) {
if (gf->l == fa) {
gf->l = cur;
}
if (gf->r == fa) {
gf->r = cur;
}
}
}
static void rotate_left(node_pointer cur) {
node_pointer fa = cur->fa;
node_pointer gf = fa->fa;
if (fa->is_auxiliary_root()) {
cur->lp = fa->lp;
fa->lp = nullptr;
}
push(fa);
push(cur);
fa->r = cur->l;
if (cur->l) {
cur->l->fa = fa;
}
cur->l = fa;
fa->fa = cur;
pull(fa);
cur->fa = gf;
if (gf) {
if (gf->l == fa) {
gf->l = cur;
}
if (gf->r == fa) {
gf->r = cur;
}
}
}
static void splay(node_pointer cur) {
push(cur);
if (cur->is_auxiliary_root()) {
return;
}
while (!cur->is_auxiliary_root()) {
node_pointer fa = cur->fa;
if (fa->is_auxiliary_root()) {
push(fa);
push(cur);
if (fa->l == cur) {
rotate_right(cur);
} else {
rotate_left(cur);
}
} else {
node_pointer gf = fa->fa;
push(gf);
push(fa);
push(cur);
if (gf->l == fa) {
if (fa->l == cur) {
rotate_right(fa);
rotate_right(cur);
} else {
rotate_left(cur);
rotate_right(cur);
}
} else if (fa->r == cur) {
rotate_left(fa);
rotate_left(cur);
} else {
rotate_right(cur);
rotate_left(cur);
}
}
}
pull(cur);
}
node_pointer expose(node_pointer cur) {
node_pointer pre = nullptr;
for (node_pointer anc = cur; anc; anc = anc->fa) {
splay(anc);
if (anc->r) {
anc->lt = owner->dashed.insert(anc->lt, ae(anc->r->fwd));
anc->r->lp = anc->lt;
}
anc->r = pre;
if (pre) {
push(pre);
anc->lt = owner->dashed.erase(pre->lp);
pre->lp = nullptr;
}
update(anc);
pre = anc;
}
splay(cur);
return pre;
}
public:
node_pointer make_node(const Info &inf) {
if (!owner) {
owner = std::make_shared<storage>();
}
owner->vertices.emplace_back(inf);
node_pointer res = &owner->vertices.back();
update(res);
return res;
}
void evert(node_pointer cur) {
expose(cur);
toggle(cur);
push(cur);
}
void link(node_pointer v, node_pointer fa) {
expose(fa);
expose(v);
v->fa = fa;
fa->r = v;
pull(fa);
}
void cut(node_pointer v) {
expose(v);
node_pointer fa = v->l;
assert(fa);
v->l = nullptr;
fa->fa = nullptr;
pull(v);
}
void set_info(node_pointer cur, const Info &inf) {
expose(cur);
cur->inf = inf;
update(cur);
}
Info get_info(node_pointer cur) const { return cur->inf; }
Path query(node_pointer rt) {
evert(rt);
return rt->fwd;
}
Path query_subtree(node_pointer rt, node_pointer rot) {
evert(rt);
expose(rot);
// rot is the bottom of the exposed path: its cached key is precisely
// its rooted subtree, excluding the ancestor path in rot->l.
assert(!rot->r);
return rot->key;
}
};
/// @brief Index-based wrapper; copies share the same forest.
/// Vertices must be valid; link distinct components and cut an existing edge.
/// The two query_subtree vertices must belong to the same component.
template <class Path, class Point, class Info, auto vtx, auto cmp, auto rk,
auto ae, auto av>
class dynamic_rerooting_dp {
using top_tree_type =
dynamic_rerooting_top_tree<Path, Point, Info, vtx, cmp, rk, ae, av>;
top_tree_type tr;
std::vector<typename top_tree_type::node_pointer> nd;
void check_vertex(int u) const {
assert(0 <= u && std::size_t(u) < nd.size());
}
public:
explicit dynamic_rerooting_dp(const std::vector<Info> &inf) : nd(inf.size()) {
assert(inf.size() <= std::size_t(std::numeric_limits<int>::max()));
for (int i = 0; i < int(inf.size()); i++) {
nd[i] = tr.make_node(inf[i]);
}
}
void link(int a, int b) {
check_vertex(a);
check_vertex(b);
tr.evert(nd[a]);
tr.link(nd[a], nd[b]);
}
void cut(int a, int b) {
check_vertex(a);
check_vertex(b);
tr.evert(nd[a]);
tr.cut(nd[b]);
}
void set_info(int idx, const Info &inf) {
check_vertex(idx);
tr.set_info(nd[idx], inf);
}
Info get_info(int idx) const {
check_vertex(idx);
return tr.get_info(nd[idx]);
}
Path query(int rt) {
check_vertex(rt);
return tr.query(nd[rt]);
}
Path query_subtree(int rt, int rot) {
check_vertex(rt);
check_vertex(rot);
return tr.query_subtree(nd[rt], nd[rot]);
}
};
} // namespace noya
// NOYA_DYNAMIC_REROOTING_TOP_TREE_HPP
#ifndef NOYA_DYNAMIC_REROOTING_TOP_TREE_HPP
#define NOYA_DYNAMIC_REROOTING_TOP_TREE_HPP 1
/// @complexity Time: O(log n) amortized per link, cut, point update, reroot,
/// or aggregate query, for O(1) DP operations. Releasing the last owner is O(n).
/// Space: O(n), including recycled nodes.
#include <algorithm>
#include <cassert>
#include <cstddef>
#include <deque>
#include <limits>
#include <memory>
#include <utility>
#include <vector>
namespace noya {
namespace dynamic_rerooting_internal {
template <class Point, auto rk> class dashed_splay_tree {
public:
struct node {
node *l = nullptr;
node *r = nullptr;
node *fa = nullptr;
Point key;
Point sum;
explicit node(const Point &val) : key(val), sum(val) {}
};
using node_pointer = node *;
private:
std::deque<node> nodes;
std::vector<node_pointer> free;
node_pointer allocate(const Point &val) {
if (free.empty()) {
nodes.emplace_back(val);
return &nodes.back();
}
node_pointer cur = free.back();
free.pop_back();
cur->l = cur->r = cur->fa = nullptr;
cur->key = cur->sum = val;
return cur;
}
static void update(node_pointer cur) {
cur->sum = cur->key;
if (cur->l) {
cur->sum = rk(cur->sum, cur->l->sum);
}
if (cur->r) {
cur->sum = rk(cur->sum, cur->r->sum);
}
}
static void rotate_right(node_pointer cur) {
node_pointer fa = cur->fa;
node_pointer gf = fa->fa;
fa->l = cur->r;
if (cur->r) {
cur->r->fa = fa;
}
cur->r = fa;
fa->fa = cur;
update(fa);
cur->fa = gf;
if (gf) {
if (gf->l == fa) {
gf->l = cur;
}
if (gf->r == fa) {
gf->r = cur;
}
}
}
static void rotate_left(node_pointer cur) {
node_pointer fa = cur->fa;
node_pointer gf = fa->fa;
fa->r = cur->l;
if (cur->l) {
cur->l->fa = fa;
}
cur->l = fa;
fa->fa = cur;
update(fa);
cur->fa = gf;
if (gf) {
if (gf->l == fa) {
gf->l = cur;
}
if (gf->r == fa) {
gf->r = cur;
}
}
}
static node_pointer rightmost(node_pointer cur) {
while (cur->r) {
cur = cur->r;
}
return cur;
}
public:
static void splay(node_pointer cur) {
if (!cur->fa) {
return;
}
while (cur->fa) {
node_pointer fa = cur->fa;
if (!fa->fa) {
if (fa->l == cur) {
rotate_right(cur);
} else {
rotate_left(cur);
}
} else {
node_pointer gf = fa->fa;
if (gf->l == fa) {
if (fa->l == cur) {
rotate_right(fa);
rotate_right(cur);
} else {
rotate_left(cur);
rotate_right(cur);
}
} else if (fa->r == cur) {
rotate_left(fa);
rotate_left(cur);
} else {
rotate_right(cur);
rotate_left(cur);
}
}
}
update(cur);
}
node_pointer insert(node_pointer rt, const Point &val) {
node_pointer ins = allocate(val);
// Rake is commutative: the previous tree can become the new root's left
// child directly, without searching for and splaying its rightmost node.
ins->l = rt;
if (rt) {
rt->fa = ins;
update(ins);
}
return ins;
}
node_pointer erase(node_pointer cur) {
splay(cur);
node_pointer l = cur->l;
node_pointer r = cur->r;
free.push_back(cur);
if (!l) {
if (r) {
r->fa = nullptr;
}
return r;
}
if (!r) {
l->fa = nullptr;
return l;
}
l->fa = nullptr;
node_pointer rt = rightmost(l);
splay(rt);
rt->r = r;
r->fa = rt;
update(rt);
return rt;
}
};
} // namespace dynamic_rerooting_internal
/// @brief Dynamic rerooting DP on a top tree represented by preferred paths.
/// `cmp` joins consecutive path clusters, while commutative `rk`
/// combines light subtrees. `ae` changes a path cluster into a point
/// cluster and `av` attaches all light clusters to one path vertex.
/// Expose moves preferred edges between the path splay and the dashed-edge
/// splay, so both forward and reversed path aggregates stay current.
/// DP operations must obey the path/rake composition laws and be pure.
/// Copies share the same forest. Stable node handles are owned by that shared
/// storage; do not delete them or use them after the last owner is released.
/// Link different components with v as a represented root; cut a nonroot.
template <class Path, class Point, class Info, auto vtx, auto cmp, auto rk,
auto ae, auto av>
class dynamic_rerooting_top_tree {
using dashed_tree = dynamic_rerooting_internal::dashed_splay_tree<Point, rk>;
struct node {
node *l = nullptr;
node *r = nullptr;
node *fa = nullptr;
Info inf;
Path key{};
Path fwd{};
Path bwd{};
typename dashed_tree::node_pointer lt = nullptr;
typename dashed_tree::node_pointer lp = nullptr;
bool rev = false;
explicit node(const Info &val) : inf(val) {}
bool is_auxiliary_root() const {
return !fa || (fa->l != this && fa->r != this);
}
};
struct storage {
std::deque<node> vertices;
dashed_tree dashed;
};
std::shared_ptr<storage> owner = std::make_shared<storage>();
public:
using node_pointer = node *;
private:
static void toggle(node_pointer cur) {
std::swap(cur->l, cur->r);
std::swap(cur->fwd, cur->bwd);
cur->rev ^= true;
}
static void push(node_pointer cur) {
if (!cur->rev) {
return;
}
if (cur->l) {
toggle(cur->l);
}
if (cur->r) {
toggle(cur->r);
}
cur->rev = false;
}
static void pull(node_pointer cur) {
Path fwd = cur->key;
Path bwd = cur->key;
if (cur->l) {
fwd = cmp(cur->l->fwd, fwd);
bwd = cmp(bwd, cur->l->bwd);
}
if (cur->r) {
fwd = cmp(fwd, cur->r->fwd);
bwd = cmp(cur->r->bwd, bwd);
}
cur->fwd = fwd;
cur->bwd = bwd;
}
static void update(node_pointer cur) {
cur->key = cur->lt ? av(cur->lt->sum, cur->inf) : vtx(cur->inf);
pull(cur);
}
static void rotate_right(node_pointer cur) {
node_pointer fa = cur->fa;
node_pointer gf = fa->fa;
if (fa->is_auxiliary_root()) {
cur->lp = fa->lp;
fa->lp = nullptr;
}
push(fa);
push(cur);
fa->l = cur->r;
if (cur->r) {
cur->r->fa = fa;
}
cur->r = fa;
fa->fa = cur;
pull(fa);
cur->fa = gf;
if (gf) {
if (gf->l == fa) {
gf->l = cur;
}
if (gf->r == fa) {
gf->r = cur;
}
}
}
static void rotate_left(node_pointer cur) {
node_pointer fa = cur->fa;
node_pointer gf = fa->fa;
if (fa->is_auxiliary_root()) {
cur->lp = fa->lp;
fa->lp = nullptr;
}
push(fa);
push(cur);
fa->r = cur->l;
if (cur->l) {
cur->l->fa = fa;
}
cur->l = fa;
fa->fa = cur;
pull(fa);
cur->fa = gf;
if (gf) {
if (gf->l == fa) {
gf->l = cur;
}
if (gf->r == fa) {
gf->r = cur;
}
}
}
static void splay(node_pointer cur) {
push(cur);
if (cur->is_auxiliary_root()) {
return;
}
while (!cur->is_auxiliary_root()) {
node_pointer fa = cur->fa;
if (fa->is_auxiliary_root()) {
push(fa);
push(cur);
if (fa->l == cur) {
rotate_right(cur);
} else {
rotate_left(cur);
}
} else {
node_pointer gf = fa->fa;
push(gf);
push(fa);
push(cur);
if (gf->l == fa) {
if (fa->l == cur) {
rotate_right(fa);
rotate_right(cur);
} else {
rotate_left(cur);
rotate_right(cur);
}
} else if (fa->r == cur) {
rotate_left(fa);
rotate_left(cur);
} else {
rotate_right(cur);
rotate_left(cur);
}
}
}
pull(cur);
}
node_pointer expose(node_pointer cur) {
node_pointer pre = nullptr;
for (node_pointer anc = cur; anc; anc = anc->fa) {
splay(anc);
if (anc->r) {
anc->lt = owner->dashed.insert(anc->lt, ae(anc->r->fwd));
anc->r->lp = anc->lt;
}
anc->r = pre;
if (pre) {
push(pre);
anc->lt = owner->dashed.erase(pre->lp);
pre->lp = nullptr;
}
update(anc);
pre = anc;
}
splay(cur);
return pre;
}
public:
node_pointer make_node(const Info &inf) {
if (!owner) {
owner = std::make_shared<storage>();
}
owner->vertices.emplace_back(inf);
node_pointer res = &owner->vertices.back();
update(res);
return res;
}
void evert(node_pointer cur) {
expose(cur);
toggle(cur);
push(cur);
}
void link(node_pointer v, node_pointer fa) {
expose(fa);
expose(v);
v->fa = fa;
fa->r = v;
pull(fa);
}
void cut(node_pointer v) {
expose(v);
node_pointer fa = v->l;
assert(fa);
v->l = nullptr;
fa->fa = nullptr;
pull(v);
}
void set_info(node_pointer cur, const Info &inf) {
expose(cur);
cur->inf = inf;
update(cur);
}
Info get_info(node_pointer cur) const { return cur->inf; }
Path query(node_pointer rt) {
evert(rt);
return rt->fwd;
}
Path query_subtree(node_pointer rt, node_pointer rot) {
evert(rt);
expose(rot);
// rot is the bottom of the exposed path: its cached key is precisely
// its rooted subtree, excluding the ancestor path in rot->l.
assert(!rot->r);
return rot->key;
}
};
/// @brief Index-based wrapper; copies share the same forest.
/// Vertices must be valid; link distinct components and cut an existing edge.
/// The two query_subtree vertices must belong to the same component.
template <class Path, class Point, class Info, auto vtx, auto cmp, auto rk,
auto ae, auto av>
class dynamic_rerooting_dp {
using top_tree_type =
dynamic_rerooting_top_tree<Path, Point, Info, vtx, cmp, rk, ae, av>;
top_tree_type tr;
std::vector<typename top_tree_type::node_pointer> nd;
void check_vertex(int u) const {
assert(0 <= u && std::size_t(u) < nd.size());
}
public:
explicit dynamic_rerooting_dp(const std::vector<Info> &inf) : nd(inf.size()) {
assert(inf.size() <= std::size_t(std::numeric_limits<int>::max()));
for (int i = 0; i < int(inf.size()); i++) {
nd[i] = tr.make_node(inf[i]);
}
}
void link(int a, int b) {
check_vertex(a);
check_vertex(b);
tr.evert(nd[a]);
tr.link(nd[a], nd[b]);
}
void cut(int a, int b) {
check_vertex(a);
check_vertex(b);
tr.evert(nd[a]);
tr.cut(nd[b]);
}
void set_info(int idx, const Info &inf) {
check_vertex(idx);
tr.set_info(nd[idx], inf);
}
Info get_info(int idx) const {
check_vertex(idx);
return tr.get_info(nd[idx]);
}
Path query(int rt) {
check_vertex(rt);
return tr.query(nd[rt]);
}
Path query_subtree(int rt, int rot) {
check_vertex(rt);
check_vertex(rot);
return tr.query_subtree(nd[rt], nd[rot]);
}
};
} // namespace noya
#endif // NOYA_DYNAMIC_REROOTING_TOP_TREE_HPP
/// @complexity Time: O(log n) amortized per link, cut, point update, reroot,
/// or aggregate query, for O(1) DP operations. Releasing the last owner is O(n).
/// Space: O(n), including recycled nodes.
#include <algorithm>
#include <cassert>
#include <cstddef>
#include <deque>
#include <limits>
#include <memory>
#include <utility>
#include <vector>
namespace noya {
namespace dynamic_rerooting_internal {
template <class Point, auto rk> class dashed_splay_tree {
public:
struct node {
node *l = nullptr;
node *r = nullptr;
node *fa = nullptr;
Point key;
Point sum;
explicit node(const Point &val) : key(val), sum(val) {}
};
using node_pointer = node *;
private:
std::deque<node> nodes;
std::vector<node_pointer> free;
node_pointer allocate(const Point &val) {
if (free.empty()) {
nodes.emplace_back(val);
return &nodes.back();
}
node_pointer cur = free.back();
free.pop_back();
cur->l = cur->r = cur->fa = nullptr;
cur->key = cur->sum = val;
return cur;
}
static void update(node_pointer cur) {
cur->sum = cur->key;
if (cur->l) {
cur->sum = rk(cur->sum, cur->l->sum);
}
if (cur->r) {
cur->sum = rk(cur->sum, cur->r->sum);
}
}
static void rotate_right(node_pointer cur) {
node_pointer fa = cur->fa;
node_pointer gf = fa->fa;
fa->l = cur->r;
if (cur->r) {
cur->r->fa = fa;
}
cur->r = fa;
fa->fa = cur;
update(fa);
cur->fa = gf;
if (gf) {
if (gf->l == fa) {
gf->l = cur;
}
if (gf->r == fa) {
gf->r = cur;
}
}
}
static void rotate_left(node_pointer cur) {
node_pointer fa = cur->fa;
node_pointer gf = fa->fa;
fa->r = cur->l;
if (cur->l) {
cur->l->fa = fa;
}
cur->l = fa;
fa->fa = cur;
update(fa);
cur->fa = gf;
if (gf) {
if (gf->l == fa) {
gf->l = cur;
}
if (gf->r == fa) {
gf->r = cur;
}
}
}
static node_pointer rightmost(node_pointer cur) {
while (cur->r) {
cur = cur->r;
}
return cur;
}
public:
static void splay(node_pointer cur) {
if (!cur->fa) {
return;
}
while (cur->fa) {
node_pointer fa = cur->fa;
if (!fa->fa) {
if (fa->l == cur) {
rotate_right(cur);
} else {
rotate_left(cur);
}
} else {
node_pointer gf = fa->fa;
if (gf->l == fa) {
if (fa->l == cur) {
rotate_right(fa);
rotate_right(cur);
} else {
rotate_left(cur);
rotate_right(cur);
}
} else if (fa->r == cur) {
rotate_left(fa);
rotate_left(cur);
} else {
rotate_right(cur);
rotate_left(cur);
}
}
}
update(cur);
}
node_pointer insert(node_pointer rt, const Point &val) {
node_pointer ins = allocate(val);
// Rake is commutative: the previous tree can become the new root's left
// child directly, without searching for and splaying its rightmost node.
ins->l = rt;
if (rt) {
rt->fa = ins;
update(ins);
}
return ins;
}
node_pointer erase(node_pointer cur) {
splay(cur);
node_pointer l = cur->l;
node_pointer r = cur->r;
free.push_back(cur);
if (!l) {
if (r) {
r->fa = nullptr;
}
return r;
}
if (!r) {
l->fa = nullptr;
return l;
}
l->fa = nullptr;
node_pointer rt = rightmost(l);
splay(rt);
rt->r = r;
r->fa = rt;
update(rt);
return rt;
}
};
} // namespace dynamic_rerooting_internal
/// @brief Dynamic rerooting DP on a top tree represented by preferred paths.
/// `cmp` joins consecutive path clusters, while commutative `rk`
/// combines light subtrees. `ae` changes a path cluster into a point
/// cluster and `av` attaches all light clusters to one path vertex.
/// Expose moves preferred edges between the path splay and the dashed-edge
/// splay, so both forward and reversed path aggregates stay current.
/// DP operations must obey the path/rake composition laws and be pure.
/// Copies share the same forest. Stable node handles are owned by that shared
/// storage; do not delete them or use them after the last owner is released.
/// Link different components with v as a represented root; cut a nonroot.
template <class Path, class Point, class Info, auto vtx, auto cmp, auto rk,
auto ae, auto av>
class dynamic_rerooting_top_tree {
using dashed_tree = dynamic_rerooting_internal::dashed_splay_tree<Point, rk>;
struct node {
node *l = nullptr;
node *r = nullptr;
node *fa = nullptr;
Info inf;
Path key{};
Path fwd{};
Path bwd{};
typename dashed_tree::node_pointer lt = nullptr;
typename dashed_tree::node_pointer lp = nullptr;
bool rev = false;
explicit node(const Info &val) : inf(val) {}
bool is_auxiliary_root() const {
return !fa || (fa->l != this && fa->r != this);
}
};
struct storage {
std::deque<node> vertices;
dashed_tree dashed;
};
std::shared_ptr<storage> owner = std::make_shared<storage>();
public:
using node_pointer = node *;
private:
static void toggle(node_pointer cur) {
std::swap(cur->l, cur->r);
std::swap(cur->fwd, cur->bwd);
cur->rev ^= true;
}
static void push(node_pointer cur) {
if (!cur->rev) {
return;
}
if (cur->l) {
toggle(cur->l);
}
if (cur->r) {
toggle(cur->r);
}
cur->rev = false;
}
static void pull(node_pointer cur) {
Path fwd = cur->key;
Path bwd = cur->key;
if (cur->l) {
fwd = cmp(cur->l->fwd, fwd);
bwd = cmp(bwd, cur->l->bwd);
}
if (cur->r) {
fwd = cmp(fwd, cur->r->fwd);
bwd = cmp(cur->r->bwd, bwd);
}
cur->fwd = fwd;
cur->bwd = bwd;
}
static void update(node_pointer cur) {
cur->key = cur->lt ? av(cur->lt->sum, cur->inf) : vtx(cur->inf);
pull(cur);
}
static void rotate_right(node_pointer cur) {
node_pointer fa = cur->fa;
node_pointer gf = fa->fa;
if (fa->is_auxiliary_root()) {
cur->lp = fa->lp;
fa->lp = nullptr;
}
push(fa);
push(cur);
fa->l = cur->r;
if (cur->r) {
cur->r->fa = fa;
}
cur->r = fa;
fa->fa = cur;
pull(fa);
cur->fa = gf;
if (gf) {
if (gf->l == fa) {
gf->l = cur;
}
if (gf->r == fa) {
gf->r = cur;
}
}
}
static void rotate_left(node_pointer cur) {
node_pointer fa = cur->fa;
node_pointer gf = fa->fa;
if (fa->is_auxiliary_root()) {
cur->lp = fa->lp;
fa->lp = nullptr;
}
push(fa);
push(cur);
fa->r = cur->l;
if (cur->l) {
cur->l->fa = fa;
}
cur->l = fa;
fa->fa = cur;
pull(fa);
cur->fa = gf;
if (gf) {
if (gf->l == fa) {
gf->l = cur;
}
if (gf->r == fa) {
gf->r = cur;
}
}
}
static void splay(node_pointer cur) {
push(cur);
if (cur->is_auxiliary_root()) {
return;
}
while (!cur->is_auxiliary_root()) {
node_pointer fa = cur->fa;
if (fa->is_auxiliary_root()) {
push(fa);
push(cur);
if (fa->l == cur) {
rotate_right(cur);
} else {
rotate_left(cur);
}
} else {
node_pointer gf = fa->fa;
push(gf);
push(fa);
push(cur);
if (gf->l == fa) {
if (fa->l == cur) {
rotate_right(fa);
rotate_right(cur);
} else {
rotate_left(cur);
rotate_right(cur);
}
} else if (fa->r == cur) {
rotate_left(fa);
rotate_left(cur);
} else {
rotate_right(cur);
rotate_left(cur);
}
}
}
pull(cur);
}
node_pointer expose(node_pointer cur) {
node_pointer pre = nullptr;
for (node_pointer anc = cur; anc; anc = anc->fa) {
splay(anc);
if (anc->r) {
anc->lt = owner->dashed.insert(anc->lt, ae(anc->r->fwd));
anc->r->lp = anc->lt;
}
anc->r = pre;
if (pre) {
push(pre);
anc->lt = owner->dashed.erase(pre->lp);
pre->lp = nullptr;
}
update(anc);
pre = anc;
}
splay(cur);
return pre;
}
public:
node_pointer make_node(const Info &inf) {
if (!owner) {
owner = std::make_shared<storage>();
}
owner->vertices.emplace_back(inf);
node_pointer res = &owner->vertices.back();
update(res);
return res;
}
void evert(node_pointer cur) {
expose(cur);
toggle(cur);
push(cur);
}
void link(node_pointer v, node_pointer fa) {
expose(fa);
expose(v);
v->fa = fa;
fa->r = v;
pull(fa);
}
void cut(node_pointer v) {
expose(v);
node_pointer fa = v->l;
assert(fa);
v->l = nullptr;
fa->fa = nullptr;
pull(v);
}
void set_info(node_pointer cur, const Info &inf) {
expose(cur);
cur->inf = inf;
update(cur);
}
Info get_info(node_pointer cur) const { return cur->inf; }
Path query(node_pointer rt) {
evert(rt);
return rt->fwd;
}
Path query_subtree(node_pointer rt, node_pointer rot) {
evert(rt);
expose(rot);
// rot is the bottom of the exposed path: its cached key is precisely
// its rooted subtree, excluding the ancestor path in rot->l.
assert(!rot->r);
return rot->key;
}
};
/// @brief Index-based wrapper; copies share the same forest.
/// Vertices must be valid; link distinct components and cut an existing edge.
/// The two query_subtree vertices must belong to the same component.
template <class Path, class Point, class Info, auto vtx, auto cmp, auto rk,
auto ae, auto av>
class dynamic_rerooting_dp {
using top_tree_type =
dynamic_rerooting_top_tree<Path, Point, Info, vtx, cmp, rk, ae, av>;
top_tree_type tr;
std::vector<typename top_tree_type::node_pointer> nd;
void check_vertex(int u) const {
assert(0 <= u && std::size_t(u) < nd.size());
}
public:
explicit dynamic_rerooting_dp(const std::vector<Info> &inf) : nd(inf.size()) {
assert(inf.size() <= std::size_t(std::numeric_limits<int>::max()));
for (int i = 0; i < int(inf.size()); i++) {
nd[i] = tr.make_node(inf[i]);
}
}
void link(int a, int b) {
check_vertex(a);
check_vertex(b);
tr.evert(nd[a]);
tr.link(nd[a], nd[b]);
}
void cut(int a, int b) {
check_vertex(a);
check_vertex(b);
tr.evert(nd[a]);
tr.cut(nd[b]);
}
void set_info(int idx, const Info &inf) {
check_vertex(idx);
tr.set_info(nd[idx], inf);
}
Info get_info(int idx) const {
check_vertex(idx);
return tr.get_info(nd[idx]);
}
Path query(int rt) {
check_vertex(rt);
return tr.query(nd[rt]);
}
Path query_subtree(int rt, int rot) {
check_vertex(rt);
check_vertex(rot);
return tr.query_subtree(nd[rt], nd[rot]);
}
};
} // namespace noya
// NOYA_DYNAMIC_REROOTING_TOP_TREE_HPP