dynamic_tree_subtree.hpp¶
在可连边断边的森林中维护以指定根观察的子树加法与子树和。
Complexity: Time: Amortized O(log n) per link, cut, vertex update, or directed-subtree operation. Space: O(n).
AC 记录：dynamic_tree_subtree_add_subtree_sum, dynamic_tree_vertex_add_subtree_sum。
Implementation¶
当前头文件，省略 include guard；依赖见 #include。
/// @complexity Time: Amortized O(log n) per link, cut, vertex update, or
/// directed-subtree operation. Space: O(n).
#include <cassert>
#include <cstdint>
#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.
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) {
if (fa != nil) {
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;
}
cur->pull(nil);
pre = cur;
}
splay(nil);
}
void make_root(node *nil) {
access(nil);
rev = !rev;
push(nil);
}
void link_to(node *np, node *nil) {
access(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())); }
public:
explicit dynamic_tree_subtree(const std::vector<long long> &va1)
: nd_(va1.size()) {
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);
nd_[u].access(none());
nd_[u].val += dlt;
nd_[u].pull(none());
}
/// @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);
nd_[fa].make_root(none());
nd_[u].cut_from_parent(none());
nd_[u].apply_add(dlt);
nd_[u].link_to(&nd_[fa], none());
}
/// @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);
nd_[fa].make_root(none());
nd_[u].cut_from_parent(none());
long long res = nd_[u].sum;
nd_[u].link_to(&nd_[fa], none());
return res;
}
};
} // namespace noya
#ifndef NOYA_DYNAMIC_TREE_SUBTREE_HPP
#define NOYA_DYNAMIC_TREE_SUBTREE_HPP 1
/// @complexity Time: Amortized O(log n) per link, cut, vertex update, or
/// directed-subtree operation. Space: O(n).
#include <cassert>
#include <cstdint>
#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.
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) {
if (fa != nil) {
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;
}
cur->pull(nil);
pre = cur;
}
splay(nil);
}
void make_root(node *nil) {
access(nil);
rev = !rev;
push(nil);
}
void link_to(node *np, node *nil) {
access(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())); }
public:
explicit dynamic_tree_subtree(const std::vector<long long> &va1)
: nd_(va1.size()) {
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);
nd_[u].access(none());
nd_[u].val += dlt;
nd_[u].pull(none());
}
/// @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);
nd_[fa].make_root(none());
nd_[u].cut_from_parent(none());
nd_[u].apply_add(dlt);
nd_[u].link_to(&nd_[fa], none());
}
/// @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);
nd_[fa].make_root(none());
nd_[u].cut_from_parent(none());
long long res = nd_[u].sum;
nd_[u].link_to(&nd_[fa], none());
return res;
}
};
} // namespace noya
#endif // NOYA_DYNAMIC_TREE_SUBTREE_HPP
#include <cassert>
#include <cstdint>
#include <vector>
/// @complexity Time: Amortized O(log n) per link, cut, vertex update, or
/// directed-subtree operation. Space: O(n).
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.
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) {
if (fa != nil) {
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;
}
cur->pull(nil);
pre = cur;
}
splay(nil);
}
void make_root(node *nil) {
access(nil);
rev = !rev;
push(nil);
}
void link_to(node *np, node *nil) {
access(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())); }
public:
explicit dynamic_tree_subtree(const std::vector<long long> &va1)
: nd_(va1.size()) {
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);
nd_[u].access(none());
nd_[u].val += dlt;
nd_[u].pull(none());
}
/// @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);
nd_[fa].make_root(none());
nd_[u].cut_from_parent(none());
nd_[u].apply_add(dlt);
nd_[u].link_to(&nd_[fa], none());
}
/// @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);
nd_[fa].make_root(none());
nd_[u].cut_from_parent(none());
long long res = nd_[u].sum;
nd_[u].link_to(&nd_[fa], none());
return res;
}
};
} // namespace noya