dynamic_tree_path_affine_sum.hpp¶
固定树上修改点值或边的仿射函数，查询任意根收到的所有点路径变换值之和。
Complexity: Time: \(O(n \log n)\) construction and \(O(\log n)\) amortized per vertex update, edge update, or root query. Space: \(O(n)\).
Source: Nyaan (path aggregation)
AC 记录：point_set_tree_path_composite_sum, point_set_tree_path_composite_sum_fixed_root。
Implementation¶
当前头文件，省略 include guard；依赖见 #include。
/// @complexity Time: O(n log n) construction and O(log n) amortized per
/// vertex update, edge update, or root query. Space: O(n).
#include "noya/graph/dynamic_rerooting_top_tree.hpp"
#include <algorithm>
#include <cassert>
#include <utility>
#include <vector>
namespace noya {
namespace dynamic_tree_path_affine_sum_internal {
template <class Mint> struct traits {
struct path {
Mint mul{};
Mint add{};
Mint sum{};
Mint cnt{};
};
struct point {
Mint sum{};
Mint cnt{};
};
struct info {
bool iv = true;
Mint a{};
Mint b{};
};
static path vertex(const info &x) {
if (x.iv) {
return {Mint(1), Mint(0), x.a, Mint(1)};
}
return {x.a, x.b, Mint(0), Mint(0)};
}
static path compress(const path &fa, const path &v) {
return {fa.mul * v.mul, fa.mul * v.add + fa.add,
fa.sum + fa.mul * v.sum + fa.add * v.cnt, fa.cnt + v.cnt};
}
static point rake(const point &a, const point &b) {
return {a.sum + b.sum, a.cnt + b.cnt};
}
static point add_edge(const path &cl) { return {cl.sum, cl.cnt}; }
static path add_vertex(const point &ch, const info &x) {
if (x.iv) {
return {Mint(1), Mint(0), ch.sum + x.a, ch.cnt + Mint(1)};
}
return {x.a, x.b, ch.sum * x.a + ch.cnt * x.b, ch.cnt};
}
};
} // namespace dynamic_tree_path_affine_sum_internal
/// @brief Maintain sums of edge-affine transforms from any chosen root.
/// Every original edge is split by an edge-node carrying its affine map. A top
/// tree cluster stores the affine transform along its boundary path, the sum
/// of all values entering that path, and their count. Compress composes paths;
/// rake adds independent branches. Preferred-path expose therefore propagates
/// a point update to the complete rerooted aggregate in logarithmic time.
/// The topology is a fixed nonempty tree; ee[e] and aff[e] describe the same
/// undirected edge, with the same map in either direction. query(r) sums, over
/// all v, val[v] transformed along v -> r (the map nearest r is outermost).
/// Supports vertex-value assignments and edge-map assignments, not link/cut.
/// Mint is a commutative semiring with default zero, construction from 0/1,
/// copy, + and *; no comparison, subtraction or division is needed. Counts
/// are stored in Mint too. Complexity assumes constant-time Mint operations.
/// All node/edge indices and 2*n-1 must fit int; inputs must describe a tree.
/// Copies share the same forest, including updates; they are not deep copies.
template <class Mint> class dynamic_tree_path_affine_sum {
using trait = dynamic_tree_path_affine_sum_internal::traits<Mint>;
using path = typename trait::path;
using point = typename trait::point;
using info = typename trait::info;
using dp_type =
dynamic_rerooting_dp<path, point, info, trait::vertex, trait::compress,
trait::rake, trait::add_edge, trait::add_vertex>;
int n;
dp_type dp;
static std::vector<info>
make_info(const std::vector<Mint> &val,
const std::vector<std::pair<Mint, Mint>> &aff) {
std::vector<info> res(val.size() + aff.size());
for (int u = 0; u < int(val.size()); u++) {
res[u] = {true, val[u], Mint(0)};
}
for (int e = 0; e < int(aff.size()); e++) {
res[val.size() + e] = {false, aff[e].first, aff[e].second};
}
return res;
}
public:
dynamic_tree_path_affine_sum(const std::vector<Mint> &val,
const std::vector<std::pair<int, int>> &ee,
const std::vector<std::pair<Mint, Mint>> &aff)
: n(int(val.size())), dp(make_info(val, aff)) {
assert(n >= 1);
assert(int(ee.size()) == n - 1);
assert(aff.size() == ee.size());
for (int e = 0; e < n - 1; e++) {
auto [a, b] = ee[e];
assert(0 <= a && a < n && 0 <= b && b < n);
dp.link(n + e, a);
dp.link(n + e, b);
}
}
void set_vertex(int u, Mint va1) {
assert(0 <= u && u < n);
dp.set_info(u, {true, va1, Mint(0)});
}
void set_edge(int e, Mint mul, Mint add) {
assert(0 <= e && e < n - 1);
dp.set_info(n + e, {false, mul, add});
}
Mint query(int rt) {
assert(0 <= rt && rt < n);
return dp.query(rt).sum;
}
};
} // namespace noya
// NOYA_DYNAMIC_TREE_PATH_AFFINE_SUM_HPP
#ifndef NOYA_DYNAMIC_TREE_PATH_AFFINE_SUM_HPP
#define NOYA_DYNAMIC_TREE_PATH_AFFINE_SUM_HPP 1
/// @complexity Time: O(n log n) construction and O(log n) amortized per
/// vertex update, edge update, or root query. Space: O(n).
#include "noya/graph/dynamic_rerooting_top_tree.hpp"
#include <algorithm>
#include <cassert>
#include <utility>
#include <vector>
namespace noya {
namespace dynamic_tree_path_affine_sum_internal {
template <class Mint> struct traits {
struct path {
Mint mul{};
Mint add{};
Mint sum{};
Mint cnt{};
};
struct point {
Mint sum{};
Mint cnt{};
};
struct info {
bool iv = true;
Mint a{};
Mint b{};
};
static path vertex(const info &x) {
if (x.iv) {
return {Mint(1), Mint(0), x.a, Mint(1)};
}
return {x.a, x.b, Mint(0), Mint(0)};
}
static path compress(const path &fa, const path &v) {
return {fa.mul * v.mul, fa.mul * v.add + fa.add,
fa.sum + fa.mul * v.sum + fa.add * v.cnt, fa.cnt + v.cnt};
}
static point rake(const point &a, const point &b) {
return {a.sum + b.sum, a.cnt + b.cnt};
}
static point add_edge(const path &cl) { return {cl.sum, cl.cnt}; }
static path add_vertex(const point &ch, const info &x) {
if (x.iv) {
return {Mint(1), Mint(0), ch.sum + x.a, ch.cnt + Mint(1)};
}
return {x.a, x.b, ch.sum * x.a + ch.cnt * x.b, ch.cnt};
}
};
} // namespace dynamic_tree_path_affine_sum_internal
/// @brief Maintain sums of edge-affine transforms from any chosen root.
/// Every original edge is split by an edge-node carrying its affine map. A top
/// tree cluster stores the affine transform along its boundary path, the sum
/// of all values entering that path, and their count. Compress composes paths;
/// rake adds independent branches. Preferred-path expose therefore propagates
/// a point update to the complete rerooted aggregate in logarithmic time.
/// The topology is a fixed nonempty tree; ee[e] and aff[e] describe the same
/// undirected edge, with the same map in either direction. query(r) sums, over
/// all v, val[v] transformed along v -> r (the map nearest r is outermost).
/// Supports vertex-value assignments and edge-map assignments, not link/cut.
/// Mint is a commutative semiring with default zero, construction from 0/1,
/// copy, + and *; no comparison, subtraction or division is needed. Counts
/// are stored in Mint too. Complexity assumes constant-time Mint operations.
/// All node/edge indices and 2*n-1 must fit int; inputs must describe a tree.
/// Copies share the same forest, including updates; they are not deep copies.
template <class Mint> class dynamic_tree_path_affine_sum {
using trait = dynamic_tree_path_affine_sum_internal::traits<Mint>;
using path = typename trait::path;
using point = typename trait::point;
using info = typename trait::info;
using dp_type =
dynamic_rerooting_dp<path, point, info, trait::vertex, trait::compress,
trait::rake, trait::add_edge, trait::add_vertex>;
int n;
dp_type dp;
static std::vector<info>
make_info(const std::vector<Mint> &val,
const std::vector<std::pair<Mint, Mint>> &aff) {
std::vector<info> res(val.size() + aff.size());
for (int u = 0; u < int(val.size()); u++) {
res[u] = {true, val[u], Mint(0)};
}
for (int e = 0; e < int(aff.size()); e++) {
res[val.size() + e] = {false, aff[e].first, aff[e].second};
}
return res;
}
public:
dynamic_tree_path_affine_sum(const std::vector<Mint> &val,
const std::vector<std::pair<int, int>> &ee,
const std::vector<std::pair<Mint, Mint>> &aff)
: n(int(val.size())), dp(make_info(val, aff)) {
assert(n >= 1);
assert(int(ee.size()) == n - 1);
assert(aff.size() == ee.size());
for (int e = 0; e < n - 1; e++) {
auto [a, b] = ee[e];
assert(0 <= a && a < n && 0 <= b && b < n);
dp.link(n + e, a);
dp.link(n + e, b);
}
}
void set_vertex(int u, Mint va1) {
assert(0 <= u && u < n);
dp.set_info(u, {true, va1, Mint(0)});
}
void set_edge(int e, Mint mul, Mint add) {
assert(0 <= e && e < n - 1);
dp.set_info(n + e, {false, mul, add});
}
Mint query(int rt) {
assert(0 <= rt && rt < n);
return dp.query(rt).sum;
}
};
} // namespace noya
#endif // NOYA_DYNAMIC_TREE_PATH_AFFINE_SUM_HPP
/// @complexity Time: O(n log n) construction and O(log n) amortized per
/// vertex update, edge update, or root query. Space: O(n).
/// @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
#include <algorithm>
#include <cassert>
#include <utility>
#include <vector>
namespace noya {
namespace dynamic_tree_path_affine_sum_internal {
template <class Mint> struct traits {
struct path {
Mint mul{};
Mint add{};
Mint sum{};
Mint cnt{};
};
struct point {
Mint sum{};
Mint cnt{};
};
struct info {
bool iv = true;
Mint a{};
Mint b{};
};
static path vertex(const info &x) {
if (x.iv) {
return {Mint(1), Mint(0), x.a, Mint(1)};
}
return {x.a, x.b, Mint(0), Mint(0)};
}
static path compress(const path &fa, const path &v) {
return {fa.mul * v.mul, fa.mul * v.add + fa.add,
fa.sum + fa.mul * v.sum + fa.add * v.cnt, fa.cnt + v.cnt};
}
static point rake(const point &a, const point &b) {
return {a.sum + b.sum, a.cnt + b.cnt};
}
static point add_edge(const path &cl) { return {cl.sum, cl.cnt}; }
static path add_vertex(const point &ch, const info &x) {
if (x.iv) {
return {Mint(1), Mint(0), ch.sum + x.a, ch.cnt + Mint(1)};
}
return {x.a, x.b, ch.sum * x.a + ch.cnt * x.b, ch.cnt};
}
};
} // namespace dynamic_tree_path_affine_sum_internal
/// @brief Maintain sums of edge-affine transforms from any chosen root.
/// Every original edge is split by an edge-node carrying its affine map. A top
/// tree cluster stores the affine transform along its boundary path, the sum
/// of all values entering that path, and their count. Compress composes paths;
/// rake adds independent branches. Preferred-path expose therefore propagates
/// a point update to the complete rerooted aggregate in logarithmic time.
/// The topology is a fixed nonempty tree; ee[e] and aff[e] describe the same
/// undirected edge, with the same map in either direction. query(r) sums, over
/// all v, val[v] transformed along v -> r (the map nearest r is outermost).
/// Supports vertex-value assignments and edge-map assignments, not link/cut.
/// Mint is a commutative semiring with default zero, construction from 0/1,
/// copy, + and *; no comparison, subtraction or division is needed. Counts
/// are stored in Mint too. Complexity assumes constant-time Mint operations.
/// All node/edge indices and 2*n-1 must fit int; inputs must describe a tree.
/// Copies share the same forest, including updates; they are not deep copies.
template <class Mint> class dynamic_tree_path_affine_sum {
using trait = dynamic_tree_path_affine_sum_internal::traits<Mint>;
using path = typename trait::path;
using point = typename trait::point;
using info = typename trait::info;
using dp_type =
dynamic_rerooting_dp<path, point, info, trait::vertex, trait::compress,
trait::rake, trait::add_edge, trait::add_vertex>;
int n;
dp_type dp;
static std::vector<info>
make_info(const std::vector<Mint> &val,
const std::vector<std::pair<Mint, Mint>> &aff) {
std::vector<info> res(val.size() + aff.size());
for (int u = 0; u < int(val.size()); u++) {
res[u] = {true, val[u], Mint(0)};
}
for (int e = 0; e < int(aff.size()); e++) {
res[val.size() + e] = {false, aff[e].first, aff[e].second};
}
return res;
}
public:
dynamic_tree_path_affine_sum(const std::vector<Mint> &val,
const std::vector<std::pair<int, int>> &ee,
const std::vector<std::pair<Mint, Mint>> &aff)
: n(int(val.size())), dp(make_info(val, aff)) {
assert(n >= 1);
assert(int(ee.size()) == n - 1);
assert(aff.size() == ee.size());
for (int e = 0; e < n - 1; e++) {
auto [a, b] = ee[e];
assert(0 <= a && a < n && 0 <= b && b < n);
dp.link(n + e, a);
dp.link(n + e, b);
}
}
void set_vertex(int u, Mint va1) {
assert(0 <= u && u < n);
dp.set_info(u, {true, va1, Mint(0)});
}
void set_edge(int e, Mint mul, Mint add) {
assert(0 <= e && e < n - 1);
dp.set_info(n + e, {false, mul, add});
}
Mint query(int rt) {
assert(0 <= rt && rt < n);
return dp.query(rt).sum;
}
};
} // namespace noya
// NOYA_DYNAMIC_TREE_PATH_AFFINE_SUM_HPP