hly1204's library
This documentation is automatically generated by competitive-verifier/competitive-verifier
test/tree/dynamic_tree_vertex_set_path_composite.0.test.cpp
- View this file on GitHub
- Last update: 2026-02-11 21:03:28+08:00
- Problem: https://judge.yosupo.jp/problem/dynamic_tree_vertex_set_path_composite
Depends on
Code
// competitive-verifier: PROBLEM https://judge.yosupo.jp/problem/dynamic_tree_vertex_set_path_composite
#include "modint.hpp"
#include "node_pool.hpp"
#include "st_tree_node_base.hpp"
#include <array>
#include <iostream>
#include <utility>
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
using mint = ModInt<998244353>;
using LinearFunction = std::array<mint, 2>;
struct STTreeNode : STTreeNodeBase<STTreeNode> {
LinearFunction Val, Sum, RevSum;
static LinearFunction composition(const LinearFunction &L, const LinearFunction &R) {
return LinearFunction{L[0] + L[1] * R[0], L[1] * R[1]};
}
void do_flip() { std::swap(Sum, RevSum); }
void do_update() {
Sum = RevSum = Val;
if (left()) {
Sum = composition(left()->Sum, Sum);
RevSum = composition(RevSum, left()->RevSum);
}
if (right()) {
Sum = composition(Sum, right()->Sum);
RevSum = composition(right()->RevSum, RevSum);
}
}
};
int n, m;
std::cin >> n >> m;
FixedSizeNodePool<STTreeNode> pool(n);
auto [node, id] = pool.get_func();
for (int i = 0; i < n; ++i) {
std::cin >> node(i)->Val[1] >> node(i)->Val[0];
node(i)->update();
}
for (int i = 0; i < n - 1; ++i) {
int u, v;
std::cin >> u >> v;
node(u)->link(node(v));
}
while (m--) {
int cmd;
std::cin >> cmd;
if (cmd == 0) {
int a, b, c, d;
std::cin >> a >> b >> c >> d;
node(a)->cut(node(b));
node(c)->link(node(d));
} else if (cmd == 1) {
int a;
std::cin >> a;
node(a)->expose();
std::cin >> node(a)->Val[1] >> node(a)->Val[0];
node(a)->update();
} else {
int a, b;
mint x;
std::cin >> a >> b >> x;
node(b)->evert();
node(a)->expose();
std::cout << STTreeNode::composition(node(a)->Sum, {x, 0}).at(0) << '\n';
}
}
return 0;
}
#line 1 "test/tree/dynamic_tree_vertex_set_path_composite.0.test.cpp"
// competitive-verifier: PROBLEM https://judge.yosupo.jp/problem/dynamic_tree_vertex_set_path_composite
#line 2 "modint.hpp"
#include <iostream>
#include <type_traits>
// clang-format off
template<unsigned Mod> class ModInt {
static_assert((Mod >> 31) == 0, "`Mod` must less than 2^(31)");
template<typename Int>
static std::enable_if_t<std::is_integral_v<Int>, unsigned> safe_mod(Int v) { using D = std::common_type_t<Int, unsigned>; return (v %= (int)Mod) < 0 ? (D)(v + (int)Mod) : (D)v; }
struct PrivateConstructor {} static inline private_constructor{};
ModInt(PrivateConstructor, unsigned v) : v_(v) {}
unsigned v_;
public:
static unsigned mod() { return Mod; }
static ModInt from_raw(unsigned v) { return ModInt(private_constructor, v); }
static ModInt zero() { return from_raw(0); }
static ModInt one() { return from_raw(1); }
bool is_zero() const { return v_ == 0; }
bool is_one() const { return v_ == 1; }
ModInt() : v_() {}
template<typename Int, typename std::enable_if_t<std::is_signed_v<Int>, int> = 0> ModInt(Int v) : v_(safe_mod(v)) {}
template<typename Int, typename std::enable_if_t<std::is_unsigned_v<Int>, int> = 0> ModInt(Int v) : v_(v % Mod) {}
unsigned val() const { return v_; }
ModInt operator-() const { return from_raw(v_ == 0 ? v_ : Mod - v_); }
ModInt pow(long long e) const { if (e < 0) return inv().pow(-e); for (ModInt x(*this), res(from_raw(1));; x *= x) { if (e & 1) res *= x; if ((e >>= 1) == 0) return res; }}
ModInt inv() const { int x1 = 1, x3 = 0, a = val(), b = Mod; while (b) { const int q = a / b, x1_old = x1, a_old = a; x1 = x3, x3 = x1_old - x3 * q, a = b, b = a_old - b * q; } return from_raw(x1 < 0 ? x1 + (int)Mod : x1); }
template<bool Odd = (Mod & 1)> std::enable_if_t<Odd, ModInt> div_by_2() const { if (v_ & 1) return from_raw((v_ + Mod) >> 1); return from_raw(v_ >> 1); }
ModInt &operator+=(const ModInt &a) { if ((v_ += a.v_) >= Mod) v_ -= Mod; return *this; }
ModInt &operator-=(const ModInt &a) { if ((v_ += Mod - a.v_) >= Mod) v_ -= Mod; return *this; }
ModInt &operator*=(const ModInt &a) { v_ = (unsigned long long)v_ * a.v_ % Mod; return *this; }
ModInt &operator/=(const ModInt &a) { return *this *= a.inv(); }
ModInt &operator++() { return *this += one(); }
ModInt operator++(int) { ModInt o(*this); *this += one(); return o; }
ModInt &operator--() { return *this -= one(); }
ModInt operator--(int) { ModInt o(*this); *this -= one(); return o; }
friend ModInt operator+(const ModInt &a, const ModInt &b) { return ModInt(a) += b; }
friend ModInt operator-(const ModInt &a, const ModInt &b) { return ModInt(a) -= b; }
friend ModInt operator*(const ModInt &a, const ModInt &b) { return ModInt(a) *= b; }
friend ModInt operator/(const ModInt &a, const ModInt &b) { return ModInt(a) /= b; }
friend bool operator==(const ModInt &a, const ModInt &b) { return a.v_ == b.v_; }
friend bool operator!=(const ModInt &a, const ModInt &b) { return a.v_ != b.v_; }
friend std::istream &operator>>(std::istream &a, ModInt &b) { int v; a >> v; b.v_ = safe_mod(v); return a; }
friend std::ostream &operator<<(std::ostream &a, const ModInt &b) { return a << b.val(); }
};
// clang-format on
#line 2 "node_pool.hpp"
#include <list>
#include <memory>
#include <utility>
#include <vector>
template<typename NodeT> class FixedSizeNodePool {
std::vector<NodeT> pool;
public:
explicit FixedSizeNodePool(int n) : pool(n) {}
NodeT *at(int ind) { return pool.data() + ind; }
int id(NodeT *a) const { return a - pool.data(); }
auto get_func() {
return std::make_pair([this](int ind) { return at(ind); },
[this](NodeT *a) { return id(a); });
}
};
template<typename NodeT> class DynamicSizeNodePool {
struct Wrapped : public NodeT {
using NodeT::NodeT;
typename std::list<Wrapped>::iterator i;
};
std::list<Wrapped> used_list;
std::list<Wrapped> free_list;
public:
template<typename... Args> NodeT *make(Args &&...arg) {
if (free_list.empty()) {
auto &&node = used_list.emplace_back(std::forward<Args>(arg)...);
node.i = std::prev(used_list.end());
return std::addressof(node);
}
used_list.splice(used_list.end(), free_list, std::prev(free_list.end()));
auto &&node = used_list.back();
node.~NodeT(); // i remains unchanged
new (std::addressof(node)) NodeT(std::forward<Args>(arg)...);
return std::addressof(node);
}
// this is lazy, if sth. relies on the order of dtor, do NOT use
void retrieve(NodeT *node) {
free_list.splice(free_list.end(), used_list, ((Wrapped *)node)->i);
}
};
#line 2 "st_tree_node_base.hpp"
#line 4 "st_tree_node_base.hpp"
template<typename STTreeNodeT> class STTreeNodeBase {
STTreeNodeBase *L;
STTreeNodeBase *R;
STTreeNodeBase *P;
int Size;
bool NeedFlip;
enum class Child { LEFT, RIGHT };
Child which() const { return P->L == this ? Child::LEFT : Child::RIGHT; }
// has NO parent OR NOT a prefered child
bool is_root() const { return P == nullptr || (P->L != this && P->R != this); }
bool is_left_child() const { return which() == Child::LEFT; }
bool is_right_child() const { return which() == Child::RIGHT; }
// CRTP reimplement
void do_flip() {}
void do_propagate() {}
void do_update() {}
protected:
void base_flip() {
NeedFlip = !NeedFlip;
std::swap(L, R);
((STTreeNodeT &)*this).do_flip();
}
// base_propagate() is called to propagate the update information to child(ren).
// There is no need to update the information combined from child(ren)
// which should be done in base_update().
void base_propagate() {
((STTreeNodeT &)*this).do_propagate();
if (NeedFlip) {
NeedFlip = false;
if (L) L->base_flip();
if (R) R->base_flip();
}
}
// base_update() is called to update the information combined from child(ren).
void base_update() {
Size = 1;
if (L) Size += L->Size;
if (R) Size += R->Size;
((STTreeNodeT &)*this).do_update();
}
void base_rotate() {
P->base_propagate();
base_propagate();
if (is_left_child()) {
if ((P->L = R)) R->P = P;
if (!P->is_root()) {
if (P->is_left_child()) P->P->L = this;
else { P->P->R = this; }
}
R = P, P = P->P, R->P = this;
R->base_update();
} else {
if ((P->R = L)) L->P = P;
if (!P->is_root()) {
if (P->is_left_child()) P->P->L = this;
else { P->P->R = this; }
}
L = P, P = P->P, L->P = this;
L->base_update();
}
}
void base_splay() {
for (base_propagate(); !is_root(); base_rotate()) {
if (!P->is_root()) {
P->P->base_propagate();
P->which() == which() ? P->base_rotate() : base_rotate();
}
}
base_update();
}
STTreeNodeBase() : L(), R(), P(), Size(1), NeedFlip() {}
public:
int size() const { return Size; }
STTreeNodeT *left() const { return (STTreeNodeT *)L; }
STTreeNodeT *right() const { return (STTreeNodeT *)R; }
void update() { base_update(); }
STTreeNodeT *expose() {
STTreeNodeBase *a = this, *lca = a;
base_splay();
a->R = nullptr;
while (a->P) {
lca = a->P;
lca->base_splay();
a->P->R = a;
a->base_rotate();
}
a->base_update();
// now a is the root of the aux. tree
return (STTreeNodeT *)lca;
}
void evert() { expose(), base_flip(); }
STTreeNodeT *root() {
expose();
STTreeNodeBase *a = this;
while (a->L) a = a->L;
a->base_splay();
return (STTreeNodeT *)a;
}
STTreeNodeT *parent() {
expose();
if (!L) return nullptr;
STTreeNodeBase *a = L;
a->base_propagate();
while (a->R) {
a = a->R;
a->base_propagate();
}
a->base_splay();
return (STTreeNodeT *)a;
}
// this op. WILL change the root
void link(STTreeNodeT *a) {
evert();
if (a->root() != (STTreeNodeT *)this) P = a;
}
// this op. will NOT change the root
void cut() {
expose();
STTreeNodeBase *b = L;
L = nullptr;
if (b) b->P = nullptr;
base_update();
}
// this op. will NOT change the root
void cut(STTreeNodeT *b) {
if (parent() == b) {
cut();
} else if (b->parent() == (STTreeNodeT *)this) {
b->cut();
}
}
STTreeNodeT *select(int k) {
// example: A --> B --> C --> D, where D is the root of the path
// We use expose(A) than:
// * size(A) = 4
// * select(A, 0) returns D
// * select(A, 1) returns C
// * ...
STTreeNodeBase *a = this;
a->base_propagate();
while ((a->L ? a->L->Size : 0) != k) {
if ((a->L ? a->L->Size : 0) < k) {
k -= (a->L ? a->L->Size : 0) + 1;
a = a->R;
} else {
a = a->L;
}
a->base_propagate();
}
a->base_splay();
return (STTreeNodeT *)a;
}
STTreeNodeT *jump(int k) { return select(Size - k - 1); }
};
#line 6 "test/tree/dynamic_tree_vertex_set_path_composite.0.test.cpp"
#include <array>
#line 9 "test/tree/dynamic_tree_vertex_set_path_composite.0.test.cpp"
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
using mint = ModInt<998244353>;
using LinearFunction = std::array<mint, 2>;
struct STTreeNode : STTreeNodeBase<STTreeNode> {
LinearFunction Val, Sum, RevSum;
static LinearFunction composition(const LinearFunction &L, const LinearFunction &R) {
return LinearFunction{L[0] + L[1] * R[0], L[1] * R[1]};
}
void do_flip() { std::swap(Sum, RevSum); }
void do_update() {
Sum = RevSum = Val;
if (left()) {
Sum = composition(left()->Sum, Sum);
RevSum = composition(RevSum, left()->RevSum);
}
if (right()) {
Sum = composition(Sum, right()->Sum);
RevSum = composition(right()->RevSum, RevSum);
}
}
};
int n, m;
std::cin >> n >> m;
FixedSizeNodePool<STTreeNode> pool(n);
auto [node, id] = pool.get_func();
for (int i = 0; i < n; ++i) {
std::cin >> node(i)->Val[1] >> node(i)->Val[0];
node(i)->update();
}
for (int i = 0; i < n - 1; ++i) {
int u, v;
std::cin >> u >> v;
node(u)->link(node(v));
}
while (m--) {
int cmd;
std::cin >> cmd;
if (cmd == 0) {
int a, b, c, d;
std::cin >> a >> b >> c >> d;
node(a)->cut(node(b));
node(c)->link(node(d));
} else if (cmd == 1) {
int a;
std::cin >> a;
node(a)->expose();
std::cin >> node(a)->Val[1] >> node(a)->Val[0];
node(a)->update();
} else {
int a, b;
mint x;
std::cin >> a >> b >> x;
node(b)->evert();
node(a)->expose();
std::cout << STTreeNode::composition(node(a)->Sum, {x, 0}).at(0) << '\n';
}
}
return 0;
}
Test cases
| Env | Name | Status | Elapsed | Memory |
|---|---|---|---|---|
| clang++ | almost_line_00 |
AC |
967 ms | 34 MB |
| clang++ | almost_line_01 |
AC |
992 ms | 34 MB |
| clang++ | example_00 |
AC |
10 ms | 22 MB |
| clang++ | example_01 |
AC |
9 ms | 20 MB |
| clang++ | issue_1216_00 |
AC |
155 ms | 34 MB |
| clang++ | max_random_00 |
AC |
772 ms | 32 MB |
| clang++ | max_random_01 |
AC |
767 ms | 30 MB |
| clang++ | max_random_02 |
AC |
761 ms | 34 MB |
| clang++ | medium_00 |
AC |
10 ms | 24 MB |
| clang++ | medium_01 |
AC |
10 ms | 24 MB |
| clang++ | medium_02 |
AC |
9 ms | 22 MB |
| clang++ | medium_03 |
AC |
9 ms | 19 MB |
| clang++ | medium_04 |
AC |
10 ms | 22 MB |
| clang++ | random_00 |
AC |
488 ms | 28 MB |
| clang++ | random_01 |
AC |
567 ms | 29 MB |
| clang++ | random_02 |
AC |
291 ms | 21 MB |
| clang++ | random_03 |
AC |
337 ms | 28 MB |
| clang++ | random_04 |
AC |
180 ms | 25 MB |
| clang++ | small_00 |
AC |
9 ms | 19 MB |
| clang++ | small_01 |
AC |
9 ms | 20 MB |
| clang++ | small_02 |
AC |
9 ms | 23 MB |
| clang++ | small_03 |
AC |
9 ms | 24 MB |
| clang++ | small_04 |
AC |
9 ms | 20 MB |