dynamic_tree_subtree.hpp¶
可连边断边的森林中，按相邻边指定一侧做子树加与求和；直接暴露目标侧，省去子树操作中的拆边接边。
Complexity: Time: \(O(n)\) construction; amortized \(O(\log (n + 1))\) per link, cut, vertex update or directed-subtree operation; \(O(1)\) size. Space: \(O(n)\).
AC 记录：dynamic_tree_subtree_add_subtree_sum, dynamic_tree_vertex_add_subtree_sum。
Implementation¶
当前头文件，省略 include guard；依赖见 #include。
/// @complexity Time: O(n) construction; amortized O(log(n+1)) per link,
/// cut, vertex update or directed-subtree operation; O(1) size. Space: O(n).
#include <cassert>
#include <cstddef>
#include <limits>
#include <vector>
namespace noya {
/// @brief Link-Cut Tree augmented with virtual-child size and sum. Access
/// moves preferred children into or out of the virtual aggregate; each node
/// remembers how much of its represented parent's lazy addition it has
/// already received, so subtree additions remain valid across preferred-path
/// changes. Vertices are [0,n), where n must fit int. Empty forests are valid.
/// link(a,b) requires different components; cut(a,b) requires an existing edge.
/// subtree_add/sum(u,p) require adjacent vertices and act on u's side of that
/// edge; p is not an arbitrary root. Values and deltas may be negative. All
/// sums, products and accumulated lazy-tag arithmetic must fit long long.
/// Nodes are owned by this object; copy/move are disabled to preserve pointers.
/// All tree operations and cleanup are iterative.
class dynamic_tree_subtree {
struct node {
node *fa = nullptr;
node *v[2] = {nullptr, nullptr};
long long val = 0;
int siz = 0;
int vsz = 0;
long long sum = 0;
long long vs = 0;
long long add = 0;
long long pas = 0;
bool rev = false;
void apply_add(long long dlt) {
val += dlt;
sum += static_cast<long long>(siz) * dlt;
vs += static_cast<long long>(vsz) * dlt;
add += dlt;
}
void push(node *nil) {
// Most exposes carry no addition; avoid touching every aggregate then.
if (fa != nil && pas != fa->add) {
apply_add(fa->add - pas);
pas = fa->add;
}
if (rev) {
v[0]->rev ^= v[0] != nil;
v[1]->rev ^= v[1] != nil;
node *tmp = v[0];
v[0] = v[1];
v[1] = tmp;
rev = false;
}
}
void pull(node *nil) {
if (v[0] != nil) {
v[0]->push(nil);
}
if (v[1] != nil) {
v[1]->push(nil);
}
siz = 1 + v[0]->siz + v[1]->siz + vsz;
sum = val + v[0]->sum + v[1]->sum + vs;
}
bool is_auxiliary_root(node *nil) const {
return fa == nil || (fa->v[0] != this && fa->v[1] != this);
}
void rotate(int dir, node *nil) {
node *nr = v[dir ^ 1];
node *mid = nr->v[dir];
if (mid != nil) {
mid->push(nil);
}
v[dir ^ 1] = mid;
if (mid != nil) {
mid->fa = this;
mid->pas = add;
}
nr->v[dir] = this;
nr->fa = fa;
nr->pas = fa->add;
if (fa->v[0] == this) {
fa->v[0] = nr;
}
if (fa->v[1] == this) {
fa->v[1] = nr;
}
fa = nr;
pas = nr->add;
pull(nil);
nr->pull(nil);
}
void splay(node *nil) {
while (!is_auxiliary_root(nil)) {
if (fa->is_auxiliary_root(nil)) {
fa->push(nil);
push(nil);
fa->rotate(fa->v[0] == this, nil);
} else {
node *gf = fa->fa;
gf->push(nil);
fa->push(nil);
push(nil);
bool pil = gf->v[0] == fa;
bool vil = fa->v[0] == this;
if (pil == vil) {
gf->rotate(pil, nil);
}
fa->rotate(vil, nil);
if (pil != vil) {
gf->rotate(pil, nil);
}
}
}
push(nil);
}
void access(node *nil) {
node *pre = nil;
for (node *cur = this; cur != nil; cur = cur->fa) {
cur->splay(nil);
if (cur->v[1] != nil) {
cur->v[1]->push(nil);
cur->vsz += cur->v[1]->siz;
cur->vs += cur->v[1]->sum;
}
cur->v[1] = pre;
if (pre != nil) {
pre->push(nil);
cur->vsz -= pre->siz;
cur->vs -= pre->sum;
}
// Moving a whole child between preferred and virtual sets preserves
// cur's total size/sum. Their cached values need no recomputation.
pre = cur;
}
splay(nil);
}
void make_root(node *nil) {
access(nil);
rev = !rev;
push(nil);
}
void link_to(node *np, node *nil) {
// make_root has already exposed this represented root.
assert(fa == nil && v[0] == nil);
np->access(nil);
np->v[1] = this;
fa = np;
pas = np->add;
np->pull(nil);
}
void cut_from_parent(node *nil) {
access(nil);
assert(v[0] != nil);
v[0]->push(nil);
v[0]->fa = nil;
v[0] = nil;
pull(nil);
}
};
node ni1;
std::vector<node> nd_;
node *none() { return &ni1; }
void check_vertex(int u) const { assert(0 <= u && u < int(nd_.size())); }
node &expose_side(int u, int parent) {
nd_[parent].make_root(none());
node &cur = nd_[u];
cur.access(none());
assert(cur.v[0] != none() && cur.v[1] == none());
// The final rotation's pull has synchronized the ancestor-side child.
assert(cur.v[0]->pas == cur.add);
return cur;
}
public:
explicit dynamic_tree_subtree(const std::vector<long long> &va1)
: nd_(va1.size()) {
assert(va1.size() <= std::size_t(std::numeric_limits<int>::max()));
ni1.fa = &ni1;
ni1.v[0] = ni1.v[1] = &ni1;
for (int u = 0; u < int(nd_.size()); u++) {
node &cur = nd_[u];
cur.fa = none();
cur.v[0] = cur.v[1] = none();
cur.val = cur.sum = va1[u];
cur.siz = 1;
}
}
dynamic_tree_subtree(const dynamic_tree_subtree &) = delete;
dynamic_tree_subtree &operator=(const dynamic_tree_subtree &) = delete;
dynamic_tree_subtree(dynamic_tree_subtree &&) = delete;
dynamic_tree_subtree &operator=(dynamic_tree_subtree &&) = delete;
int size() const { return int(nd_.size()); }
/// @brief Link two different represented trees with an undirected edge.
void link(int a, int b) {
check_vertex(a);
check_vertex(b);
nd_[a].make_root(none());
nd_[a].link_to(&nd_[b], none());
}
/// @brief Remove an existing undirected edge.
void cut(int a, int b) {
check_vertex(a);
check_vertex(b);
nd_[a].make_root(none());
nd_[b].cut_from_parent(none());
}
/// @brief Add dlt to vertex u.
void vertex_add(int u, long long dlt) {
check_vertex(u);
if (dlt == 0)
return;
nd_[u].access(none());
nd_[u].val += dlt;
nd_[u].sum += dlt;
}
/// @brief Add dlt to the component on u's side after conceptually
/// removing the adjacent edge (u,fa), then restore that edge.
void subtree_add(int u, int fa, long long dlt) {
check_vertex(u);
check_vertex(fa);
if (dlt == 0)
return;
node &cur = expose_side(u, fa);
cur.val += dlt;
cur.vs += static_cast<long long>(cur.vsz) * dlt;
cur.sum += static_cast<long long>(1 + cur.vsz) * dlt;
cur.add += dlt;
// Only the vertex and its virtual descendants receive this increment.
// Cancel it for the exposed ancestor side, without cutting the edge.
cur.v[0]->pas = cur.add;
}
/// @brief Sum the component on u's side after conceptually removing
/// the adjacent edge (u,fa), then restore that edge.
long long subtree_sum(int u, int fa) {
check_vertex(u);
check_vertex(fa);
node &cur = expose_side(u, fa);
return cur.val + cur.vs;
}
};
} // namespace noya
// NOYA_DYNAMIC_TREE_SUBTREE_HPP
#ifndef NOYA_DYNAMIC_TREE_SUBTREE_HPP
#define NOYA_DYNAMIC_TREE_SUBTREE_HPP 1
/// @complexity Time: O(n) construction; amortized O(log(n+1)) per link,
/// cut, vertex update or directed-subtree operation; O(1) size. Space: O(n).
#include <cassert>
#include <cstddef>
#include <limits>
#include <vector>
namespace noya {
/// @brief Link-Cut Tree augmented with virtual-child size and sum. Access
/// moves preferred children into or out of the virtual aggregate; each node
/// remembers how much of its represented parent's lazy addition it has
/// already received, so subtree additions remain valid across preferred-path
/// changes. Vertices are [0,n), where n must fit int. Empty forests are valid.
/// link(a,b) requires different components; cut(a,b) requires an existing edge.
/// subtree_add/sum(u,p) require adjacent vertices and act on u's side of that
/// edge; p is not an arbitrary root. Values and deltas may be negative. All
/// sums, products and accumulated lazy-tag arithmetic must fit long long.
/// Nodes are owned by this object; copy/move are disabled to preserve pointers.
/// All tree operations and cleanup are iterative.
class dynamic_tree_subtree {
struct node {
node *fa = nullptr;
node *v[2] = {nullptr, nullptr};
long long val = 0;
int siz = 0;
int vsz = 0;
long long sum = 0;
long long vs = 0;
long long add = 0;
long long pas = 0;
bool rev = false;
void apply_add(long long dlt) {
val += dlt;
sum += static_cast<long long>(siz) * dlt;
vs += static_cast<long long>(vsz) * dlt;
add += dlt;
}
void push(node *nil) {
// Most exposes carry no addition; avoid touching every aggregate then.
if (fa != nil && pas != fa->add) {
apply_add(fa->add - pas);
pas = fa->add;
}
if (rev) {
v[0]->rev ^= v[0] != nil;
v[1]->rev ^= v[1] != nil;
node *tmp = v[0];
v[0] = v[1];
v[1] = tmp;
rev = false;
}
}
void pull(node *nil) {
if (v[0] != nil) {
v[0]->push(nil);
}
if (v[1] != nil) {
v[1]->push(nil);
}
siz = 1 + v[0]->siz + v[1]->siz + vsz;
sum = val + v[0]->sum + v[1]->sum + vs;
}
bool is_auxiliary_root(node *nil) const {
return fa == nil || (fa->v[0] != this && fa->v[1] != this);
}
void rotate(int dir, node *nil) {
node *nr = v[dir ^ 1];
node *mid = nr->v[dir];
if (mid != nil) {
mid->push(nil);
}
v[dir ^ 1] = mid;
if (mid != nil) {
mid->fa = this;
mid->pas = add;
}
nr->v[dir] = this;
nr->fa = fa;
nr->pas = fa->add;
if (fa->v[0] == this) {
fa->v[0] = nr;
}
if (fa->v[1] == this) {
fa->v[1] = nr;
}
fa = nr;
pas = nr->add;
pull(nil);
nr->pull(nil);
}
void splay(node *nil) {
while (!is_auxiliary_root(nil)) {
if (fa->is_auxiliary_root(nil)) {
fa->push(nil);
push(nil);
fa->rotate(fa->v[0] == this, nil);
} else {
node *gf = fa->fa;
gf->push(nil);
fa->push(nil);
push(nil);
bool pil = gf->v[0] == fa;
bool vil = fa->v[0] == this;
if (pil == vil) {
gf->rotate(pil, nil);
}
fa->rotate(vil, nil);
if (pil != vil) {
gf->rotate(pil, nil);
}
}
}
push(nil);
}
void access(node *nil) {
node *pre = nil;
for (node *cur = this; cur != nil; cur = cur->fa) {
cur->splay(nil);
if (cur->v[1] != nil) {
cur->v[1]->push(nil);
cur->vsz += cur->v[1]->siz;
cur->vs += cur->v[1]->sum;
}
cur->v[1] = pre;
if (pre != nil) {
pre->push(nil);
cur->vsz -= pre->siz;
cur->vs -= pre->sum;
}
// Moving a whole child between preferred and virtual sets preserves
// cur's total size/sum. Their cached values need no recomputation.
pre = cur;
}
splay(nil);
}
void make_root(node *nil) {
access(nil);
rev = !rev;
push(nil);
}
void link_to(node *np, node *nil) {
// make_root has already exposed this represented root.
assert(fa == nil && v[0] == nil);
np->access(nil);
np->v[1] = this;
fa = np;
pas = np->add;
np->pull(nil);
}
void cut_from_parent(node *nil) {
access(nil);
assert(v[0] != nil);
v[0]->push(nil);
v[0]->fa = nil;
v[0] = nil;
pull(nil);
}
};
node ni1;
std::vector<node> nd_;
node *none() { return &ni1; }
void check_vertex(int u) const { assert(0 <= u && u < int(nd_.size())); }
node &expose_side(int u, int parent) {
nd_[parent].make_root(none());
node &cur = nd_[u];
cur.access(none());
assert(cur.v[0] != none() && cur.v[1] == none());
// The final rotation's pull has synchronized the ancestor-side child.
assert(cur.v[0]->pas == cur.add);
return cur;
}
public:
explicit dynamic_tree_subtree(const std::vector<long long> &va1)
: nd_(va1.size()) {
assert(va1.size() <= std::size_t(std::numeric_limits<int>::max()));
ni1.fa = &ni1;
ni1.v[0] = ni1.v[1] = &ni1;
for (int u = 0; u < int(nd_.size()); u++) {
node &cur = nd_[u];
cur.fa = none();
cur.v[0] = cur.v[1] = none();
cur.val = cur.sum = va1[u];
cur.siz = 1;
}
}
dynamic_tree_subtree(const dynamic_tree_subtree &) = delete;
dynamic_tree_subtree &operator=(const dynamic_tree_subtree &) = delete;
dynamic_tree_subtree(dynamic_tree_subtree &&) = delete;
dynamic_tree_subtree &operator=(dynamic_tree_subtree &&) = delete;
int size() const { return int(nd_.size()); }
/// @brief Link two different represented trees with an undirected edge.
void link(int a, int b) {
check_vertex(a);
check_vertex(b);
nd_[a].make_root(none());
nd_[a].link_to(&nd_[b], none());
}
/// @brief Remove an existing undirected edge.
void cut(int a, int b) {
check_vertex(a);
check_vertex(b);
nd_[a].make_root(none());
nd_[b].cut_from_parent(none());
}
/// @brief Add dlt to vertex u.
void vertex_add(int u, long long dlt) {
check_vertex(u);
if (dlt == 0)
return;
nd_[u].access(none());
nd_[u].val += dlt;
nd_[u].sum += dlt;
}
/// @brief Add dlt to the component on u's side after conceptually
/// removing the adjacent edge (u,fa), then restore that edge.
void subtree_add(int u, int fa, long long dlt) {
check_vertex(u);
check_vertex(fa);
if (dlt == 0)
return;
node &cur = expose_side(u, fa);
cur.val += dlt;
cur.vs += static_cast<long long>(cur.vsz) * dlt;
cur.sum += static_cast<long long>(1 + cur.vsz) * dlt;
cur.add += dlt;
// Only the vertex and its virtual descendants receive this increment.
// Cancel it for the exposed ancestor side, without cutting the edge.
cur.v[0]->pas = cur.add;
}
/// @brief Sum the component on u's side after conceptually removing
/// the adjacent edge (u,fa), then restore that edge.
long long subtree_sum(int u, int fa) {
check_vertex(u);
check_vertex(fa);
node &cur = expose_side(u, fa);
return cur.val + cur.vs;
}
};
} // namespace noya
#endif // NOYA_DYNAMIC_TREE_SUBTREE_HPP
/// @complexity Time: O(n) construction; amortized O(log(n+1)) per link,
/// cut, vertex update or directed-subtree operation; O(1) size. Space: O(n).
#include <cassert>
#include <cstddef>
#include <limits>
#include <vector>
namespace noya {
/// @brief Link-Cut Tree augmented with virtual-child size and sum. Access
/// moves preferred children into or out of the virtual aggregate; each node
/// remembers how much of its represented parent's lazy addition it has
/// already received, so subtree additions remain valid across preferred-path
/// changes. Vertices are [0,n), where n must fit int. Empty forests are valid.
/// link(a,b) requires different components; cut(a,b) requires an existing edge.
/// subtree_add/sum(u,p) require adjacent vertices and act on u's side of that
/// edge; p is not an arbitrary root. Values and deltas may be negative. All
/// sums, products and accumulated lazy-tag arithmetic must fit long long.
/// Nodes are owned by this object; copy/move are disabled to preserve pointers.
/// All tree operations and cleanup are iterative.
class dynamic_tree_subtree {
struct node {
node *fa = nullptr;
node *v[2] = {nullptr, nullptr};
long long val = 0;
int siz = 0;
int vsz = 0;
long long sum = 0;
long long vs = 0;
long long add = 0;
long long pas = 0;
bool rev = false;
void apply_add(long long dlt) {
val += dlt;
sum += static_cast<long long>(siz) * dlt;
vs += static_cast<long long>(vsz) * dlt;
add += dlt;
}
void push(node *nil) {
// Most exposes carry no addition; avoid touching every aggregate then.
if (fa != nil && pas != fa->add) {
apply_add(fa->add - pas);
pas = fa->add;
}
if (rev) {
v[0]->rev ^= v[0] != nil;
v[1]->rev ^= v[1] != nil;
node *tmp = v[0];
v[0] = v[1];
v[1] = tmp;
rev = false;
}
}
void pull(node *nil) {
if (v[0] != nil) {
v[0]->push(nil);
}
if (v[1] != nil) {
v[1]->push(nil);
}
siz = 1 + v[0]->siz + v[1]->siz + vsz;
sum = val + v[0]->sum + v[1]->sum + vs;
}
bool is_auxiliary_root(node *nil) const {
return fa == nil || (fa->v[0] != this && fa->v[1] != this);
}
void rotate(int dir, node *nil) {
node *nr = v[dir ^ 1];
node *mid = nr->v[dir];
if (mid != nil) {
mid->push(nil);
}
v[dir ^ 1] = mid;
if (mid != nil) {
mid->fa = this;
mid->pas = add;
}
nr->v[dir] = this;
nr->fa = fa;
nr->pas = fa->add;
if (fa->v[0] == this) {
fa->v[0] = nr;
}
if (fa->v[1] == this) {
fa->v[1] = nr;
}
fa = nr;
pas = nr->add;
pull(nil);
nr->pull(nil);
}
void splay(node *nil) {
while (!is_auxiliary_root(nil)) {
if (fa->is_auxiliary_root(nil)) {
fa->push(nil);
push(nil);
fa->rotate(fa->v[0] == this, nil);
} else {
node *gf = fa->fa;
gf->push(nil);
fa->push(nil);
push(nil);
bool pil = gf->v[0] == fa;
bool vil = fa->v[0] == this;
if (pil == vil) {
gf->rotate(pil, nil);
}
fa->rotate(vil, nil);
if (pil != vil) {
gf->rotate(pil, nil);
}
}
}
push(nil);
}
void access(node *nil) {
node *pre = nil;
for (node *cur = this; cur != nil; cur = cur->fa) {
cur->splay(nil);
if (cur->v[1] != nil) {
cur->v[1]->push(nil);
cur->vsz += cur->v[1]->siz;
cur->vs += cur->v[1]->sum;
}
cur->v[1] = pre;
if (pre != nil) {
pre->push(nil);
cur->vsz -= pre->siz;
cur->vs -= pre->sum;
}
// Moving a whole child between preferred and virtual sets preserves
// cur's total size/sum. Their cached values need no recomputation.
pre = cur;
}
splay(nil);
}
void make_root(node *nil) {
access(nil);
rev = !rev;
push(nil);
}
void link_to(node *np, node *nil) {
// make_root has already exposed this represented root.
assert(fa == nil && v[0] == nil);
np->access(nil);
np->v[1] = this;
fa = np;
pas = np->add;
np->pull(nil);
}
void cut_from_parent(node *nil) {
access(nil);
assert(v[0] != nil);
v[0]->push(nil);
v[0]->fa = nil;
v[0] = nil;
pull(nil);
}
};
node ni1;
std::vector<node> nd_;
node *none() { return &ni1; }
void check_vertex(int u) const { assert(0 <= u && u < int(nd_.size())); }
node &expose_side(int u, int parent) {
nd_[parent].make_root(none());
node &cur = nd_[u];
cur.access(none());
assert(cur.v[0] != none() && cur.v[1] == none());
// The final rotation's pull has synchronized the ancestor-side child.
assert(cur.v[0]->pas == cur.add);
return cur;
}
public:
explicit dynamic_tree_subtree(const std::vector<long long> &va1)
: nd_(va1.size()) {
assert(va1.size() <= std::size_t(std::numeric_limits<int>::max()));
ni1.fa = &ni1;
ni1.v[0] = ni1.v[1] = &ni1;
for (int u = 0; u < int(nd_.size()); u++) {
node &cur = nd_[u];
cur.fa = none();
cur.v[0] = cur.v[1] = none();
cur.val = cur.sum = va1[u];
cur.siz = 1;
}
}
dynamic_tree_subtree(const dynamic_tree_subtree &) = delete;
dynamic_tree_subtree &operator=(const dynamic_tree_subtree &) = delete;
dynamic_tree_subtree(dynamic_tree_subtree &&) = delete;
dynamic_tree_subtree &operator=(dynamic_tree_subtree &&) = delete;
int size() const { return int(nd_.size()); }
/// @brief Link two different represented trees with an undirected edge.
void link(int a, int b) {
check_vertex(a);
check_vertex(b);
nd_[a].make_root(none());
nd_[a].link_to(&nd_[b], none());
}
/// @brief Remove an existing undirected edge.
void cut(int a, int b) {
check_vertex(a);
check_vertex(b);
nd_[a].make_root(none());
nd_[b].cut_from_parent(none());
}
/// @brief Add dlt to vertex u.
void vertex_add(int u, long long dlt) {
check_vertex(u);
if (dlt == 0)
return;
nd_[u].access(none());
nd_[u].val += dlt;
nd_[u].sum += dlt;
}
/// @brief Add dlt to the component on u's side after conceptually
/// removing the adjacent edge (u,fa), then restore that edge.
void subtree_add(int u, int fa, long long dlt) {
check_vertex(u);
check_vertex(fa);
if (dlt == 0)
return;
node &cur = expose_side(u, fa);
cur.val += dlt;
cur.vs += static_cast<long long>(cur.vsz) * dlt;
cur.sum += static_cast<long long>(1 + cur.vsz) * dlt;
cur.add += dlt;
// Only the vertex and its virtual descendants receive this increment.
// Cancel it for the exposed ancestor side, without cutting the edge.
cur.v[0]->pas = cur.add;
}
/// @brief Sum the component on u's side after conceptually removing
/// the adjacent edge (u,fa), then restore that edge.
long long subtree_sum(int u, int fa) {
check_vertex(u);
check_vertex(fa);
node &cur = expose_side(u, fa);
return cur.val + cur.vs;
}
};
} // namespace noya
// NOYA_DYNAMIC_TREE_SUBTREE_HPP