proconlib
This documentation is automatically generated by online-judge-tools/verification-helper
test/heavy_light_decomposition.test.cpp
- View this file on GitHub
- Last update: 2022-01-07 22:21:35+09:00
- Problem: https://judge.yosupo.jp/problem/vertex_set_path_composite
Depends on
- container/segment_tree.cpp
- graph/basic_graph.cpp
- graph/tree_manager.cpp
- internal/enable_avx2.cpp
- math/rem_euclid.cpp
- math/static_modint.cpp
- math/totient.cpp
- traits/affine_composite_monoid.cpp
- traits/reversed_monoid.cpp
- utility/bit_width.cpp
- utility/ceil_log2.cpp
- utility/countl_zero.cpp
- utility/index_offset.cpp
- utility/int_alias.cpp
- utility/rec_lambda.cpp
- utility/rep.cpp
- utility/revrep.cpp
Code
#define PROBLEM "https://judge.yosupo.jp/problem/vertex_set_path_composite"
#include <iostream>
#include <vector>
#include "../container/segment_tree.cpp"
#include "../graph/basic_graph.cpp"
#include "../graph/tree_manager.cpp"
#include "../math/static_modint.cpp"
#include "../traits/affine_composite_monoid.cpp"
#include "../traits/reversed_monoid.cpp"
#include "../utility/int_alias.cpp"
#include "../utility/rep.cpp"
using Fp = Modint998244353;
using Line = Affine<Fp>;
using Monoid = AffineCompositeMonoid<Fp>;
using RevMonoid = ReversedMonoid<Monoid>;
int main() {
int N, Q;
std::cin >> N >> Q;
std::vector<Line> F(N);
for (auto& f : F) {
u32 x, y;
std::cin >> x >> y;
f = Line(x, y);
}
BasicGraph graph(N);
for (const auto _ : rep(1, N)) {
int x, y;
std::cin >> x >> y;
graph.add_edge(x, y);
graph.add_edge(y, x);
}
TreeManager tree(graph);
SegmentTree<Monoid> seg;
SegmentTree<RevMonoid> seg_rev;
{
std::vector<Line> build(N);
for (const auto i : rep(0, N)) {
build[tree[i].enter] = F[i];
}
seg = SegmentTree<Monoid>(build);
seg_rev = SegmentTree<RevMonoid>(build);
}
while (Q--) {
int t;
std::cin >> t;
if (t == 0) {
int p;
u32 c, d;
std::cin >> p >> c >> d;
F[p] = Line(c, d);
seg.assign(tree[p].enter, F[p]);
seg_rev.assign(tree[p].enter, F[p]);
} else {
int u, v;
u32 x;
std::cin >> u >> v >> x;
const auto lca = tree.lca(u, v);
Line sum_u, sum_v;
for (const auto [a, b] : tree.path(u, lca)) {
sum_u = sum_u.composite(seg_rev.fold(tree[b].enter, tree[a].enter + 1));
}
for (const auto [a, b] : tree.path(v, lca)) {
sum_v = seg.fold(tree[b].enter, tree[a].enter + 1).composite(sum_v);
}
std::cout << sum_u.composite(F[lca]).composite(sum_v).eval(x) << '\n';
}
}
return 0;
}#line 1 "test/heavy_light_decomposition.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/vertex_set_path_composite"
#include <iostream>
#include <vector>
#line 2 "container/segment_tree.cpp"
#include <cassert>
#line 2 "internal/enable_avx2.cpp"
#ifdef ENABLE_AVX2
#define TARGET_AVX2 __attribute__((target("avx2")))
#else
#define TARGET_AVX2
#endif
#line 2 "utility/int_alias.cpp"
#include <cstdint>
using i32 = std::int32_t;
using u32 = std::uint32_t;
using i64 = std::int64_t;
using u64 = std::uint64_t;
using i128 = __int128_t;
using u128 = __uint128_t;
#line 4 "utility/countl_zero.cpp"
TARGET_AVX2 constexpr int countl_zero(u64 x) {
#ifdef __GNUC__
return x == 0 ? 64 : __builtin_clzll(x);
#else
x |= x >> 1;
x |= x >> 2;
x |= x >> 4;
x |= x >> 8;
x |= x >> 16;
x |= x >> 32;
return 64 - countr_zero(~x);
#endif
}
#line 4 "utility/bit_width.cpp"
TARGET_AVX2 constexpr int bit_width(const u64 x) { return 64 - countl_zero(x); }
#line 5 "utility/ceil_log2.cpp"
TARGET_AVX2 constexpr int ceil_log2(const u64 x) {
#ifdef __GNUC__
return x == 0 ? 0 : bit_width(x - 1);
#else
int e = 0;
while (((u64)1 << e) < x) ++e;
return e;
#endif
}
#line 2 "utility/rep.cpp"
#include <algorithm>
class Range {
struct Iter {
int itr;
constexpr Iter(const int pos) noexcept : itr(pos) {}
constexpr void operator++() noexcept { ++itr; }
constexpr bool operator!=(const Iter& other) const noexcept { return itr != other.itr; }
constexpr int operator*() const noexcept { return itr; }
};
const Iter first, last;
public:
explicit constexpr Range(const int first, const int last) noexcept : first(first), last(std::max(first, last)) {}
constexpr Iter begin() const noexcept { return first; }
constexpr Iter end() const noexcept { return last; }
};
constexpr Range rep(const int l, const int r) noexcept { return Range(l, r); }
constexpr Range rep(const int n) noexcept { return Range(0, n); }
#line 3 "utility/revrep.cpp"
class ReversedRange {
struct Iter {
int itr;
constexpr Iter(const int pos) noexcept : itr(pos) {}
constexpr void operator++() noexcept { --itr; }
constexpr bool operator!=(const Iter& other) const noexcept { return itr != other.itr; }
constexpr int operator*() const noexcept { return itr; }
};
const Iter first, last;
public:
explicit constexpr ReversedRange(const int first, const int last) noexcept
: first(last - 1), last(std::min(first, last) - 1) {}
constexpr Iter begin() const noexcept { return first; }
constexpr Iter end() const noexcept { return last; }
};
constexpr ReversedRange revrep(const int l, const int r) noexcept { return ReversedRange(l, r); }
constexpr ReversedRange revrep(const int n) noexcept { return ReversedRange(0, n); }
#line 7 "container/segment_tree.cpp"
template <class M> class SegmentTree {
using T = typename M::Type;
int internal_size, seg_size;
std::vector<T> data;
void fetch(const int k) { data[k] = M::operation(data[2 * k], data[2 * k + 1]); }
public:
explicit SegmentTree(const int size = 0, const T& value = M::identity())
: SegmentTree(std::vector<T>(size, value)) {}
explicit SegmentTree(const std::vector<T>& vec) : internal_size(vec.size()) {
seg_size = 1 << ceil_log2(internal_size);
data = std::vector<T>(2 * seg_size, M::identity());
for (const int i : rep(internal_size)) data[seg_size + i] = vec[i];
for (const int i : revrep(1, seg_size)) fetch(i);
}
int size() const { return internal_size; }
void assign(int i, const T& value) {
assert(0 <= i and i < internal_size);
i += seg_size;
data[i] = value;
while (i > 1) {
i >>= 1;
fetch(i);
}
}
T fold() const { return data[1]; }
T fold(int l, int r) const {
assert(0 <= l and l <= r and r <= internal_size);
l += seg_size;
r += seg_size;
T ret_l = M::identity(), ret_r = M::identity();
while (l < r) {
if (l & 1) ret_l = M::operation(ret_l, data[l++]);
if (r & 1) ret_r = M::operation(data[--r], ret_r);
l >>= 1;
r >>= 1;
}
return M::operation(ret_l, ret_r);
}
template <class F> int max_right(int l, const F& f) const {
assert(0 <= l and l <= internal_size);
assert(f(M::identity()));
if (l == internal_size) return internal_size;
l += seg_size;
T sum = M::identity();
do {
while (!(l & 1)) l >>= 1;
if (!f(M::operation(sum, data[l]))) {
while (l < seg_size) {
l = 2 * l;
if (f(M::operation(sum, data[l]))) sum = M::operation(sum, data[l++]);
}
return l - seg_size;
}
sum = M::operation(sum, data[l++]);
} while ((l & -l) != l);
return internal_size;
}
template <class F> int min_left(int r, const F& f) const {
assert(0 <= r and r <= internal_size);
assert(f(M::identity()));
if (r == 0) return 0;
r += seg_size;
T sum = M::identity();
do {
r -= 1;
while (r > 1 and (r & 1)) r >>= 1;
if (!f(M::operation(data[r], sum))) {
while (r < seg_size) {
r = 2 * r + 1;
if (f(M::operation(data[r], sum))) sum = M::operation(data[r--], sum);
}
return r + 1 - seg_size;
}
sum = M::operation(data[r], sum);
} while ((r & -r) != r);
return 0;
}
};
#line 3 "graph/basic_graph.cpp"
#include <utility>
#line 3 "utility/index_offset.cpp"
class IndexOffset {
int offset, len;
public:
constexpr IndexOffset() noexcept : offset(), len() {}
explicit constexpr IndexOffset(const int o, const int l) noexcept : offset(o), len(l) {}
constexpr int size() const { return len; }
constexpr int operator[](const int i) const noexcept {
assert(i < len);
return offset + i;
}
constexpr int to_idx(const int i) const noexcept {
assert(offset <= i and i < offset + len);
return i - offset;
}
};
#line 6 "graph/basic_graph.cpp"
template <class E = int> class BasicGraph {
std::vector<std::vector<E>> graph;
public:
BasicGraph() : graph() {}
explicit BasicGraph(const int n) : graph(n) {}
class EdgePtr {
friend class BasicGraph;
int u, e;
BasicGraph* self;
explicit EdgePtr(const int u, const int e, BasicGraph* p) : u(u), e(e), self(p) {}
public:
EdgePtr() : u(0), e(0), self(nullptr) {}
int src() const { return u; }
E& operator*() const { return self->graph[u][e]; }
E* operator->() const { return &self->graph[u][e]; }
};
int size() const { return graph.size(); }
std::vector<E>& operator[](const int u) {
assert(0 <= u and u < size());
return graph[u];
}
const std::vector<E>& operator[](const int u) const {
assert(0 <= u and u < size());
return graph[u];
}
int add_vertex() {
graph.emplace_back();
return size() - 1;
}
IndexOffset add_vertices(int n) {
IndexOffset ret(size(), n);
while (n--) graph.emplace_back();
return ret;
}
template <class... Args> EdgePtr add_edge(const int u, Args&&... args) {
assert(0 <= u and u < size());
const int e = graph[u].size();
graph[u].emplace_back(std::forward<Args>(args)...);
return EdgePtr(u, e, this);
}
};
#line 4 "graph/tree_manager.cpp"
#include <variant>
#line 2 "utility/rec_lambda.cpp"
#include <type_traits>
#line 4 "utility/rec_lambda.cpp"
template <class F> struct RecursiveLambda : private F {
explicit constexpr RecursiveLambda(F&& f) : F(std::forward<F>(f)) {}
template <class... Args> constexpr decltype(auto) operator()(Args&&... args) const {
return F::operator()(*this, std::forward<Args>(args)...);
}
};
template <class F> constexpr decltype(auto) rec_lambda(F&& f) { return RecursiveLambda<F>(std::forward<F>(f)); }
#line 7 "graph/tree_manager.cpp"
template <class G> class TreeManager {
public:
struct NodeInfo {
int parent, subtree, head, next, enter, exit;
};
class Path {
friend class TreeManager;
int src, dst;
const TreeManager* self;
explicit Path(const int s, const int d, const TreeManager* p) : src(s), dst(d), self(p) {}
public:
Path begin() const { return *this; }
std::monostate end() const { return {}; }
bool operator!=(std::monostate) const { return src != dst; }
void operator++() { src = self->node[src].parent; }
std::pair<int, int> operator*() {
const int x = src;
const int y = self->node[src].head;
const int z = self->node[dst].next;
src = (y != self->node[dst].head ? y : z);
return {x, src};
}
};
private:
std::vector<NodeInfo> node;
public:
TreeManager() : node() {}
explicit TreeManager(const G& graph, const int root = 0) : TreeManager(graph, std::vector<int>({root})) {}
explicit TreeManager(const G& graph, const std::vector<int>& root) : node(graph.size(), NodeInfo{0, 0, 0, 0, 0, 0}) {
const int n = size();
const auto build = rec_lambda([&](auto&& dfs, const int u, const int p) -> void {
node[u].parent = p;
node[u].subtree = 1;
for (const int v : graph[u]) {
if (v != p) {
dfs(v, u);
node[u].subtree += node[v].subtree;
}
}
});
int time_stamp = 0;
const auto decompose = rec_lambda([&](auto&& dfs, const int u, const int h) -> void {
node[u].head = h;
node[u].enter = time_stamp++;
int& s = node[u].next;
s = u;
for (const int v : graph[u])
if (v != node[u].parent and (s == u or node[s].subtree < node[v].subtree)) s = v;
if (s != u) {
dfs(s, h);
for (const int v : graph[u])
if (v != node[u].parent and v != s) dfs(v, v);
}
node[u].exit = time_stamp;
});
for (const int r : root) {
assert(0 <= r and r < n);
assert(node[r].subtree == 0);
build(r, r);
decompose(r, r);
}
}
int size() const { return node.size(); }
const NodeInfo& operator[](const int u) const {
assert(0 <= u and u < size());
return node[u];
}
int lca(int u, int v) const {
assert(0 <= u and u < size());
assert(0 <= v and v < size());
if (node[u].enter > node[v].enter) std::swap(u, v);
while (node[u].enter < node[v].enter) {
if (node[u].head == node[v].head) return u;
v = node[node[v].head].parent;
}
return v;
}
Path path(const int des, const int anc) const {
assert(0 <= des and des < size());
assert(0 <= anc and anc < size());
assert(node[anc].enter <= node[des].enter and node[des].exit <= node[anc].exit);
return Path(des, anc, this);
}
};
#line 2 "math/static_modint.cpp"
#include <ostream>
#line 3 "math/rem_euclid.cpp"
template <class T> constexpr T rem_euclid(T value, const T& mod) {
assert(mod > 0);
return (value %= mod) >= 0 ? value : value + mod;
}
#line 2 "math/totient.cpp"
template <class T> constexpr T totient(T x) {
T ret = x;
for (T i = 2; i * i <= x; ++i) {
if (x % i == 0) {
ret /= i;
ret *= i - 1;
while (x % i == 0) x /= i;
}
}
if (x > 1) {
ret /= x;
ret *= x - 1;
}
return ret;
}
#line 7 "math/static_modint.cpp"
template <u32 MOD, std::enable_if_t<((u32)1 <= MOD and MOD <= ((u32)1 << 31))>* = nullptr> class StaticModint {
using Self = StaticModint;
static inline constexpr u32 PHI = totient(MOD);
u32 v;
public:
static constexpr u32 mod() noexcept { return MOD; }
template <class T, std::enable_if_t<std::is_integral_v<T>>* = nullptr>
static constexpr T normalize(const T& x) noexcept {
return rem_euclid<std::common_type_t<T, i64>>(x, MOD);
}
constexpr StaticModint() noexcept : v(0) {}
template <class T> constexpr StaticModint(const T& x) noexcept : v(normalize(x)) {}
template <class T> static constexpr Self raw(const T& x) noexcept {
Self ret;
ret.v = x;
return ret;
}
constexpr u32 val() const noexcept { return v; }
constexpr Self neg() const noexcept { return raw(v == 0 ? 0 : MOD - v); }
constexpr Self inv() const noexcept { return pow(PHI - 1); }
constexpr Self pow(u64 exp) const noexcept {
Self ret(1), mult(*this);
for (; exp > 0; exp >>= 1) {
if (exp & 1) ret *= mult;
mult *= mult;
}
return ret;
}
constexpr Self operator-() const noexcept { return neg(); }
constexpr Self operator~() const noexcept { return inv(); }
constexpr Self operator+(const Self& rhs) const noexcept { return Self(*this) += rhs; }
constexpr Self& operator+=(const Self& rhs) noexcept {
if ((v += rhs.v) >= MOD) v -= MOD;
return *this;
}
constexpr Self operator-(const Self& rhs) const noexcept { return Self(*this) -= rhs; }
constexpr Self& operator-=(const Self& rhs) noexcept {
if (v < rhs.v) v += MOD;
v -= rhs.v;
return *this;
}
constexpr Self operator*(const Self& rhs) const noexcept { return Self(*this) *= rhs; }
constexpr Self& operator*=(const Self& rhs) noexcept {
v = (u64)v * rhs.v % MOD;
return *this;
}
constexpr Self operator/(const Self& rhs) const noexcept { return Self(*this) /= rhs; }
constexpr Self& operator/=(const Self& rhs) noexcept { return *this *= rhs.inv(); }
constexpr bool operator==(const Self& rhs) const noexcept { return v == rhs.v; }
constexpr bool operator!=(const Self& rhs) const noexcept { return v != rhs.v; }
friend std::ostream& operator<<(std::ostream& stream, const Self& rhs) { return stream << rhs.v; }
};
using Modint1000000007 = StaticModint<1000000007>;
using Modint998244353 = StaticModint<998244353>;
#line 2 "traits/affine_composite_monoid.cpp"
template <class T> struct Affine {
T a, b;
constexpr Affine(const T& a = 1, const T& b = 0) : a(a), b(b) {}
constexpr T eval(const T& x) const { return a * x + b; }
constexpr Affine operator+(const Affine& other) const { return affine(a + other.a, b + other.b); }
constexpr Affine composite(const Affine& other) const { return Affine(a * other.a, b * other.a + other.b); }
};
template <class T> struct AffineCompositeMonoid {
using Type = Affine<T>;
static constexpr Type identity() { return Type(); }
static constexpr Type operation(const Type& l, const Type& r) noexcept { return l.composite(r); }
};
#line 2 "traits/reversed_monoid.cpp"
template <class M> struct ReversedMonoid {
using Type = typename M::Type;
static constexpr Type identity() { return M::identity(); }
static constexpr Type operation(const Type& l, const Type& r) { return M::operation(r, l); }
};
#line 12 "test/heavy_light_decomposition.test.cpp"
using Fp = Modint998244353;
using Line = Affine<Fp>;
using Monoid = AffineCompositeMonoid<Fp>;
using RevMonoid = ReversedMonoid<Monoid>;
int main() {
int N, Q;
std::cin >> N >> Q;
std::vector<Line> F(N);
for (auto& f : F) {
u32 x, y;
std::cin >> x >> y;
f = Line(x, y);
}
BasicGraph graph(N);
for (const auto _ : rep(1, N)) {
int x, y;
std::cin >> x >> y;
graph.add_edge(x, y);
graph.add_edge(y, x);
}
TreeManager tree(graph);
SegmentTree<Monoid> seg;
SegmentTree<RevMonoid> seg_rev;
{
std::vector<Line> build(N);
for (const auto i : rep(0, N)) {
build[tree[i].enter] = F[i];
}
seg = SegmentTree<Monoid>(build);
seg_rev = SegmentTree<RevMonoid>(build);
}
while (Q--) {
int t;
std::cin >> t;
if (t == 0) {
int p;
u32 c, d;
std::cin >> p >> c >> d;
F[p] = Line(c, d);
seg.assign(tree[p].enter, F[p]);
seg_rev.assign(tree[p].enter, F[p]);
} else {
int u, v;
u32 x;
std::cin >> u >> v >> x;
const auto lca = tree.lca(u, v);
Line sum_u, sum_v;
for (const auto [a, b] : tree.path(u, lca)) {
sum_u = sum_u.composite(seg_rev.fold(tree[b].enter, tree[a].enter + 1));
}
for (const auto [a, b] : tree.path(v, lca)) {
sum_v = seg.fold(tree[b].enter, tree[a].enter + 1).composite(sum_v);
}
std::cout << sum_u.composite(F[lca]).composite(sum_v).eval(x) << '\n';
}
}
return 0;
}