This documentation is automatically generated by online-judge-tools/verification-helper
View the Project on GitHub Harui-i/library
#define PROBLEM "https://judge.yosupo.jp/problem/vertex_set_path_composite" #include "template/template.hpp" #include <vector> #ifdef _MSC_VER #include <intrin.h> #endif namespace atcoder { namespace internal { // @param n `0 <= n` // @return minimum non-negative `x` s.t. `n <= 2**x` int ceil_pow2(int n) { int x = 0; while ((1U << x) < (unsigned int)(n)) x++; return x; } // @param n `1 <= n` // @return minimum non-negative `x` s.t. `(n & (1 << x)) != 0` constexpr int bsf_constexpr(unsigned int n) { int x = 0; while (!(n & (1 << x))) x++; return x; } // @param n `1 <= n` // @return minimum non-negative `x` s.t. `(n & (1 << x)) != 0` int bsf(unsigned int n) { #ifdef _MSC_VER unsigned long index; _BitScanForward(&index, n); return index; #else return __builtin_ctz(n); #endif } } // namespace internal } // namespace atcoder namespace atcoder { template <class S, S (*op)(S, S), S (*e)()> struct segtree { public: segtree() : segtree(0) {} explicit segtree(int n) : segtree(std::vector<S>(n, e())) {} explicit segtree(const std::vector<S>& v) : _n(int(v.size())) { log = internal::ceil_pow2(_n); size = 1 << log; d = std::vector<S>(2 * size, e()); for (int i = 0; i < _n; i++) d[size + i] = v[i]; for (int i = size - 1; i >= 1; i--) { update(i); } } void set(int p, S x) { assert(0 <= p && p < _n); p += size; d[p] = x; for (int i = 1; i <= log; i++) update(p >> i); } S get(int p) const { assert(0 <= p && p < _n); return d[p + size]; } S prod(int l, int r) const { assert(0 <= l && l <= r && r <= _n); S sml = e(), smr = e(); l += size; r += size; while (l < r) { if (l & 1) sml = op(sml, d[l++]); if (r & 1) smr = op(d[--r], smr); l >>= 1; r >>= 1; } return op(sml, smr); } S all_prod() const { return d[1]; } template <bool (*f)(S)> int max_right(int l) const { return max_right(l, [](S x) { return f(x); }); } template <class F> int max_right(int l, F f) const { assert(0 <= l && l <= _n); assert(f(e())); if (l == _n) return _n; l += size; S sm = e(); do { while (l % 2 == 0) l >>= 1; if (!f(op(sm, d[l]))) { while (l < size) { l = (2 * l); if (f(op(sm, d[l]))) { sm = op(sm, d[l]); l++; } } return l - size; } sm = op(sm, d[l]); l++; } while ((l & -l) != l); return _n; } template <bool (*f)(S)> int min_left(int r) const { return min_left(r, [](S x) { return f(x); }); } template <class F> int min_left(int r, F f) const { assert(0 <= r && r <= _n); assert(f(e())); if (r == 0) return 0; r += size; S sm = e(); do { r--; while (r > 1 && (r % 2)) r >>= 1; if (!f(op(d[r], sm))) { while (r < size) { r = (2 * r + 1); if (f(op(d[r], sm))) { sm = op(d[r], sm); r--; } } return r + 1 - size; } sm = op(d[r], sm); } while ((r & -r) != r); return 0; } private: int _n, size, log; std::vector<S> d; void update(int k) { d[k] = op(d[2 * k], d[2 * k + 1]); } }; } // namespace atcoder #include "math/linear_function.hpp" #include "math/modint.hpp" #include "graph/tree/heavy_light_decomposition.hpp" using mint = modint998244353; using LF = LinearFunction<mint>; LF op(LF l, LF r) { return l * r; } LF revop(LF l, LF r) { return r * l; } LF e() { return LF::Mul_Identity(); } int main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); int N, Q; cin >> N >> Q; vector<LF>a(N); for(int i=0; i<N; i++) { int coef_a, coef_b; cin >> coef_a >> coef_b; a[i] = LF(coef_a, coef_b); } HLD hld(N); for(int i=0; i<N-1; i++) { int u, v; cin >> u >> v; hld.graph.add_edge(u,v); hld.graph.add_edge(v,u); } hld.build(); atcoder::segtree<LF,op,e> seg(N); atcoder::segtree<LF,revop,e> revseg(N); for(int i=0; i<N; i++) { seg.set(hld.id[i], a[i]); revseg.set(hld.id[i], a[i]); } for (int q=0; q<Q; q++) { int op; cin >> op; if (op == 0) { int p, c, d; cin >> p >> c >> d; seg.set(hld.id[p], LF(c,d)); revseg.set(hld.id[p], LF(c,d)); } else if (op == 1) { int u, v; cin >> u >> v; mint x; cin >> x; LF ret = LF::Mul_Identity(); Path path = hld.get_path(u,v); for (Interval interval : path) { if (interval.reverse == true) { ret = ret * revseg.prod(interval.top_id, interval.bottom_id + 1); } else { ret = ret * seg.prod(interval.top_id, interval.bottom_id + 1); } } mint ans = ret(x); cout << ans.val() << endl; } } return 0; }
#line 1 "test/verify/yosupo-vertex-set-path-composite.test.cpp" #define PROBLEM "https://judge.yosupo.jp/problem/vertex_set_path_composite" #line 1 "template/template.hpp" #include <iostream> #include <cassert> using namespace std; using ll = long long; template<class T> inline bool chmax(T& a, const T& b) {if (a<b) {a=b; return true;} return false;} template<class T> inline bool chmin(T& a, const T& b) {if (b<a) {a=b; return true;} return false;} const int INTINF = 1000001000; const int INTMAX = 2147483647; const ll LLMAX = 9223372036854775807; const ll LLINF = 1000000000000000000; #line 3 "test/verify/yosupo-vertex-set-path-composite.test.cpp" #include <vector> #ifdef _MSC_VER #include <intrin.h> #endif namespace atcoder { namespace internal { // @param n `0 <= n` // @return minimum non-negative `x` s.t. `n <= 2**x` int ceil_pow2(int n) { int x = 0; while ((1U << x) < (unsigned int)(n)) x++; return x; } // @param n `1 <= n` // @return minimum non-negative `x` s.t. `(n & (1 << x)) != 0` constexpr int bsf_constexpr(unsigned int n) { int x = 0; while (!(n & (1 << x))) x++; return x; } // @param n `1 <= n` // @return minimum non-negative `x` s.t. `(n & (1 << x)) != 0` int bsf(unsigned int n) { #ifdef _MSC_VER unsigned long index; _BitScanForward(&index, n); return index; #else return __builtin_ctz(n); #endif } } // namespace internal } // namespace atcoder namespace atcoder { template <class S, S (*op)(S, S), S (*e)()> struct segtree { public: segtree() : segtree(0) {} explicit segtree(int n) : segtree(std::vector<S>(n, e())) {} explicit segtree(const std::vector<S>& v) : _n(int(v.size())) { log = internal::ceil_pow2(_n); size = 1 << log; d = std::vector<S>(2 * size, e()); for (int i = 0; i < _n; i++) d[size + i] = v[i]; for (int i = size - 1; i >= 1; i--) { update(i); } } void set(int p, S x) { assert(0 <= p && p < _n); p += size; d[p] = x; for (int i = 1; i <= log; i++) update(p >> i); } S get(int p) const { assert(0 <= p && p < _n); return d[p + size]; } S prod(int l, int r) const { assert(0 <= l && l <= r && r <= _n); S sml = e(), smr = e(); l += size; r += size; while (l < r) { if (l & 1) sml = op(sml, d[l++]); if (r & 1) smr = op(d[--r], smr); l >>= 1; r >>= 1; } return op(sml, smr); } S all_prod() const { return d[1]; } template <bool (*f)(S)> int max_right(int l) const { return max_right(l, [](S x) { return f(x); }); } template <class F> int max_right(int l, F f) const { assert(0 <= l && l <= _n); assert(f(e())); if (l == _n) return _n; l += size; S sm = e(); do { while (l % 2 == 0) l >>= 1; if (!f(op(sm, d[l]))) { while (l < size) { l = (2 * l); if (f(op(sm, d[l]))) { sm = op(sm, d[l]); l++; } } return l - size; } sm = op(sm, d[l]); l++; } while ((l & -l) != l); return _n; } template <bool (*f)(S)> int min_left(int r) const { return min_left(r, [](S x) { return f(x); }); } template <class F> int min_left(int r, F f) const { assert(0 <= r && r <= _n); assert(f(e())); if (r == 0) return 0; r += size; S sm = e(); do { r--; while (r > 1 && (r % 2)) r >>= 1; if (!f(op(d[r], sm))) { while (r < size) { r = (2 * r + 1); if (f(op(d[r], sm))) { sm = op(d[r], sm); r--; } } return r + 1 - size; } sm = op(d[r], sm); } while ((r & -r) != r); return 0; } private: int _n, size, log; std::vector<S> d; void update(int k) { d[k] = op(d[2 * k], d[2 * k + 1]); } }; } // namespace atcoder #line 1 "math/linear_function.hpp" template <typename T> struct LinearFunction { T a, b; LinearFunction() : a{0}, b(0) {} LinearFunction(T _a, T _b) : a(_a), b(_b) {} static LinearFunction Add_Identity() { return LinearFunction(T(0), T(0)); } static LinearFunction Mul_Identity(){ return LinearFunction(T(1), T(0)); } // f(g()) LinearFunction composite(LinearFunction& g) const { return LinearFunction(a * g.a, a * g.b + b); } LinearFunction operator+(const LinearFunction& rhs) const { return LinearFunction(a + rhs.a, b + rhs.b); } // rhs(f()) LinearFunction operator*(const LinearFunction& rhs) const { LinearFunction f = *this; return rhs.composite(f); } T operator()(T x) const { return a * x + b; } }; #line 1 "math/modint.hpp" #line 1 "math/external_gcd.hpp" #include <tuple> // g,x,y template<typename T> constexpr std::tuple<T, T, T> extendedGCD(T a, T b) { T x0 = 1, y0 = 0, x1 = 0, y1 = 1; while (b != 0) { T q = a / b; T r = a % b; a = b; b = r; T xTemp = x0 - q * x1; x0 = x1; x1 = xTemp; T yTemp = y0 - q * y1; y0 = y1; y1 = yTemp; } return {a, x0, y0}; } #line 5 "math/modint.hpp" template<int MOD> struct static_modint { int value; constexpr explicit static_modint() : value(0) {} constexpr static_modint(long long v) { value = int(((v % MOD) + MOD) % MOD); } constexpr static_modint& operator+=(const static_modint& other) { if ((value += other.value) >= MOD) value -= MOD; return *this; } constexpr static_modint& operator-=(const static_modint& other) { if ((value -= other.value) < 0) value += MOD; return *this; } constexpr static_modint& operator*=(const static_modint& other) { value = int((long long)value * other.value % MOD); return *this; } constexpr static_modint operator+(const static_modint& other) const { return static_modint(*this) += other; } constexpr static_modint operator-(const static_modint& other) const { return static_modint(*this) -= other; } constexpr static_modint operator*(const static_modint& other) const { return static_modint(*this) *= other; } constexpr static_modint pow(long long exp) const { static_modint base = *this, res = static_modint(1); while (exp > 0) { if (exp & 1) res *= base; base *= base; exp >>= 1; } return res; } constexpr static_modint inv() const { //return pow(MOD - 2); int g,x,y; tie(g,x,y) = extendedGCD(value, MOD); assert(g==1); if (x < 0) { x += MOD; } //cerr << g << " " << x << " " << y << " " << value << endl; //assert((((long)x*value)%MOD + MOD)%MOD == 1); return x; } constexpr static_modint& operator/=(const static_modint& other) { return *this *= other.inv(); } constexpr static_modint operator/(const static_modint& other) const { return static_modint(*this) /= other; } constexpr bool operator!=(const static_modint& other) const { return val() != other.val(); } constexpr bool operator==(const static_modint& other) const { return val() == other.val(); } int val() const { return this->value; } friend std::ostream& operator<<(std::ostream& os, const static_modint& mi) { return os << mi.value; } friend std::istream& operator>>(std::istream& is, static_modint& mi) { long long x; is >> x; mi = static_modint(x); return is; } }; template <int mod> using modint = static_modint<mod>; using modint998244353 = modint<998244353>; using modint1000000007 = modint<1000000007>; #line 1 "graph/tree/heavy_light_decomposition.hpp" #line 5 "graph/tree/heavy_light_decomposition.hpp" #include <algorithm> #line 7 "graph/tree/heavy_light_decomposition.hpp" #include <utility> #line 1 "graph/graph_template.hpp" #line 5 "graph/graph_template.hpp" template <typename T> struct Edge { int from; int to; T cost; // default constructor Edge () : from(-1), to(-1), cost(T(0)) {} Edge(int _from, int _to, T _cost) : from(_from), to(_to), cost(_cost) {} // unweighted Edge(int _from, int _to) : from(_from), to(_to), cost(T(1)) {} bool operator==(const Edge& rhs) const { return from == rhs.from && to == rhs.to && cost == rhs.cost; } bool operator<(const Edge& rhs) const { return cost < rhs.cost; } bool operator>(const Edge& rhs) const { return cost > rhs.cost; } }; template <typename T> struct Graph : std::vector<std::vector<Edge<T>>> { using std::vector<std::vector<Edge<T>>>::vector; // inherit constructors void add_edge(int i, Edge<T> e) { (*this)[i].push_back(e); } void add_edge(Edge<T> e) { (*this)[e.from].push_back(e); } // weighted void add_edge(int _from, int _to, T _cost) { (*this)[_from].push_back(Edge(_from, _to, _cost)); } // unweighted void add_edge(int _from, int _to) { (*this)[_from].push_back(Edge(_from, _to, T(1))); } }; #line 10 "graph/tree/heavy_light_decomposition.hpp" // cf : https://ngtkana.hatenablog.com/entry/2024/06/24/200138 struct Interval { // top_id : interval のもっとも根に近い頂点のid // bottom_id : interval のもっとも葉に近い頂点のid // last : LCAを含む interval であるかどうか // reverse : from → to と top → bottomが逆向きかどうか int top_id, bottom_id; bool last; bool reverse; Interval(int _top_id, int _bottom_id, bool _last, bool _reverse) : top_id(_top_id), bottom_id(_bottom_id), last(_last), reverse(_reverse) { } }; using Path = std::vector<Interval>; struct HLD { //vector<vector<int>>children; std::vector<int>parent; std::vector<int> id; std::vector<int> id2; std::vector<int> head; std::vector<int>depth; Graph<int>graph; HLD (int N) : parent(std::vector<int>(N, -1)), id(std::vector<int>(N)), id2(std::vector<int>(N)), head(std::vector<int>(N)), depth(std::vector<int>(N)), graph(N) {} void build(int root=0) { dfs_sz(root); int k = 0; dfs_hld(root, k); } int dfs_sz(int v) { int ret = 1, mx_sz = 0; for (Edge<int>& nxt : graph[v]) { if (nxt.to == parent[v]) continue; parent[nxt.to] = v; depth[nxt.to] = depth[v] + 1; int sz = dfs_sz(nxt.to); ret += sz; if (mx_sz < sz) { mx_sz = sz; std::swap(graph[v][0], nxt); } } return ret; } void dfs_hld(int v, int& k) { id[v] = k; k++; for (Edge e : graph[v]) { if (e.to == parent[v]) continue; head[e.to] = (e == graph[v][0] ? head[v] : e.to); dfs_hld(e.to, k); } id2[v] = k; } int lca(int u, int v) { while (true) { if (id[u] > id[v]) std::swap(u, v); if (head[u] == head[v]) return u; v = parent[head[v]]; } } Path get_path(int u, int v) { Path upath, vpath; while (head[u] != head[v]) { // ちなみにu,vのdepthの大小関係は変わり続けることもある。 // 10 → 12など。 // v's head is deeper if (depth[head[v]] >= depth[head[u]]) { assert(depth[head[v]] >= depth[head[u]]); /* / : heavy edge .... : light edge head[u] / /... u ... / head[v] / \ / \ / v */ // u→v なのでreverse=false vpath.emplace_back(id[head[v]], id[v], false, false); v = parent[head[v]]; } // u's head is deeper else if (depth[head[v]] < depth[head[u]]) { /* / : heavy edge .... : light edge head[v] / /... v ... / head[u] / \ / \ / u */ // upath.emplace_back(id[head[u]], id[u], false, true); u = parent[head[u]]; } } // v is deeper /* u / / ←↓ / v */ if (depth[v] > depth[u]) { upath.emplace_back(id[u], id[v], true, false); } // u is deeper /* v / / →↑ / u */ else { upath.emplace_back(id[v], id[u], true, true); } Path retpath = upath; std::reverse(vpath.begin(), vpath.end()); for (Interval path : vpath) retpath.push_back(path); return retpath; } std::pair<int,int> subtree_query(int r) { assert(r < int(id.size())); return std::make_pair(id[r], id2[r]); } }; #line 156 "test/verify/yosupo-vertex-set-path-composite.test.cpp" using mint = modint998244353; using LF = LinearFunction<mint>; LF op(LF l, LF r) { return l * r; } LF revop(LF l, LF r) { return r * l; } LF e() { return LF::Mul_Identity(); } int main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); int N, Q; cin >> N >> Q; vector<LF>a(N); for(int i=0; i<N; i++) { int coef_a, coef_b; cin >> coef_a >> coef_b; a[i] = LF(coef_a, coef_b); } HLD hld(N); for(int i=0; i<N-1; i++) { int u, v; cin >> u >> v; hld.graph.add_edge(u,v); hld.graph.add_edge(v,u); } hld.build(); atcoder::segtree<LF,op,e> seg(N); atcoder::segtree<LF,revop,e> revseg(N); for(int i=0; i<N; i++) { seg.set(hld.id[i], a[i]); revseg.set(hld.id[i], a[i]); } for (int q=0; q<Q; q++) { int op; cin >> op; if (op == 0) { int p, c, d; cin >> p >> c >> d; seg.set(hld.id[p], LF(c,d)); revseg.set(hld.id[p], LF(c,d)); } else if (op == 1) { int u, v; cin >> u >> v; mint x; cin >> x; LF ret = LF::Mul_Identity(); Path path = hld.get_path(u,v); for (Interval interval : path) { if (interval.reverse == true) { ret = ret * revseg.prod(interval.top_id, interval.bottom_id + 1); } else { ret = ret * seg.prod(interval.top_id, interval.bottom_id + 1); } } mint ans = ret(x); cout << ans.val() << endl; } } return 0; }