This documentation is automatically generated by online-judge-tools/verification-helper
View the Project on GitHub ningenMe/compro-library
#define PROBLEM "https://judge.yosupo.jp/problem/vertex_set_path_composite" #include <vector> #include <iostream> #include <cassert> #include <map> #include <algorithm> #include <stack> #include <numeric> #include <array> using namespace std; #include "../../lib/40-graph/Graph.cpp" #include "../../lib/40-graph/StaticTree.cpp" #include "../../lib/00-util/ModInt.cpp" #include "../../lib/10-segment-tree/SegmentTree.cpp" #include "../../lib/99-operator/monoid/MonoidRangeCompositePointUpdate.cpp" //一次関数 template<class T> struct MonoidRangeRevCompositePointUpdate { using TypeNode = T; inline static constexpr TypeNode unit_node = make_pair(1,0); inline static constexpr TypeNode func_fold(TypeNode l,TypeNode r){return {l.first*r.first,l.first*r.second+l.second};} inline static constexpr TypeNode func_operate(TypeNode l,TypeNode r){return r;} inline static constexpr bool func_check(TypeNode nodeVal,TypeNode var){return var == nodeVal;} }; using modint = ModInt<998244353>; int main(void){ cin.tie(0);ios::sync_with_stdio(false); int N,Q; cin >> N >> Q; SegmentTree<MonoidRangeCompositePointUpdate<pair<modint,modint>>> segLtoR(N,{1,0}); SegmentTree<MonoidRangeRevCompositePointUpdate<pair<modint,modint>>> segRtoL(N,{1,0}); vector<int> A(N),B(N); for(int i=0;i<N;++i) cin >> A[i] >> B[i]; Graph<int> g(N); for(int i=0;i+1<N;++i) { int u,v; cin >> u >> v; g.make_bidirectional_edge(u,v,1); } auto tree = StaticTree<StaticTreeOperator<int>>::builder(g).root(0).parent().child().subtree_size().heavy_light_decomposition().build(); for(int i=0;i<N;++i) { int j = tree.hld[i]; segLtoR.operate(j,{A[i],B[i]}); segRtoL.operate(j,{A[i],B[i]}); } while(Q--) { int q; cin >> q; if(q==0) { int i,a,b; cin >> i >> a >> b; int j = tree.hld[i]; segLtoR.operate(j,{a,b}); segRtoL.operate(j,{a,b}); } else { int l,r,x; cin >> l >> r >> x; auto tp = tree.vertex_ordered_set_on_path(l,r); pair<modint,modint> line = {1,0}; for(auto& p:tp.first) { auto tmp = segRtoL.fold(p.first,p.second+1); line = {tmp.first*line.first,tmp.first*line.second+tmp.second}; } for(auto& p:tp.second) { auto tmp = segLtoR.fold(p.first,p.second+1); line = {tmp.first*line.first,tmp.first*line.second+tmp.second}; } cout << line.first*x+line.second << "\n"; } } return 0; }
#line 1 "test/graph/Tree-hld-vertex-3.test.cpp" #define PROBLEM "https://judge.yosupo.jp/problem/vertex_set_path_composite" #include <vector> #include <iostream> #include <cassert> #include <map> #include <algorithm> #include <stack> #include <numeric> #include <array> using namespace std; #line 1 "lib/40-graph/Graph.cpp" /* * @title Graph * @docs md/graph/Graph.md */ template<class T> class Graph{ private: const size_t N,H,W; public: vector<vector<pair<size_t,T>>> edges; Graph(const size_t N):H(-1),W(-1),N(N), edges(N) {} Graph(const size_t H, const size_t W):H(H),W(W),N(H*W), edges(H*W) {} inline void make_edge(size_t from, size_t to, T w) { edges[from].emplace_back(to,w); } //{from_y,from_x} -> {to_y,to_x} inline void make_edge(pair<size_t,size_t> from, pair<size_t,size_t> to, T w) { make_edge(from.first*W+from.second,to.first*W+to.second,w); } inline void make_bidirectional_edge(size_t from, size_t to, T w) { make_edge(from,to,w); make_edge(to,from,w); } inline void make_bidirectional_edge(pair<size_t,size_t> from, pair<size_t,size_t> to, T w) { make_edge(from.first*W+from.second,to.first*W+to.second,w); make_edge(to.first*W+to.second,from.first*W+from.second,w); } inline size_t size(){return N;} inline size_t idx(pair<size_t,size_t> yx){return yx.first*W+yx.second;} }; #line 1 "lib/40-graph/StaticTree.cpp" /* * @title StaticTree - 木 * @docs md/graph/StaticTree.md */ template<class Operator> class StaticTreeBuilder; template<class Operator> class StaticTree { private: using TypeEdge = typename Operator::TypeEdge; size_t num; size_t ord; Graph<TypeEdge>& g; friend StaticTreeBuilder<Operator>; StaticTree(Graph<TypeEdge>& graph): g(graph), num(graph.size()), depth(graph.size(),-1), order(graph.size()), edge_dist(graph.size()){ } //for make_depth void dfs(int curr, int prev){ for(const auto& e:g.edges[curr]){ const int& next = e.first; if(next==prev) continue; depth[next] = depth[curr] + 1; edge_dist[next] = Operator::func_edge_merge(edge_dist[curr],e.second); dfs(next,curr); order[ord++] = next; } } //for make_eulertour void dfs(int from){ eulertour.push_back(from); for(auto& e:child[from]){ int to = e.first; dfs(to); eulertour.push_back(from); } } void make_root(const int root) { depth[root] = 0; edge_dist[root] = Operator::unit_edge; ord = 0; dfs(root,-1); order[ord++] = root; reverse_copy(order.begin(),order.end(),back_inserter(reorder)); } void make_root() { ord = 0; for(int i=0;i<num;++i) { if(depth[i]!=-1) continue; depth[i] = 0; edge_dist[i] = Operator::unit_edge; dfs(i,-1); order[ord++] = i; } reverse_copy(order.begin(),order.end(),back_inserter(reorder)); } void make_child(const int root = 0) { child.resize(num); for (size_t i = 0; i < num; ++i) for (auto& e : g.edges[i]) if (depth[i] < depth[e.first]) child[i].push_back(e); } void make_subtree_size() { subtree_size.resize(num,1); for (size_t i:order) for (auto e : child[i]) subtree_size[i] += subtree_size[e.first]; } void make_parent() { parent.resize(num,make_pair(num,Operator::unit_edge)); for (size_t i = 0; i < num; ++i) for (auto& e : g.edges[i]) if (depth[i] > depth[e.first]) parent[i] = e; } void make_ancestor() { ancestor.resize(num); for (size_t i = 0; i < num; ++i) ancestor[i][0] = (parent[i].first!=num?parent[i]:make_pair(i,Operator::unit_lca_edge)); for (size_t j = 1; j < Operator::bit; ++j) { for (size_t i = 0; i < num; ++i) { size_t k = ancestor[i][j - 1].first; ancestor[i][j] = Operator::func_lca_edge_merge(ancestor[k][j - 1],ancestor[i][j - 1]); } } } pair<size_t,TypeEdge> lca_impl(size_t l, size_t r) { if (depth[l] < depth[r]) swap(l, r); int diff = depth[l] - depth[r]; auto ancl = make_pair(l,Operator::unit_lca_edge); auto ancr = make_pair(r,Operator::unit_lca_edge); for (int j = 0; j < Operator::bit; ++j) { if (diff & (1 << j)) ancl = Operator::func_lca_edge_merge(ancestor[ancl.first][j],ancl); } if(ancl.first==ancr.first) return ancl; for (int j = Operator::bit - 1; 0 <= j; --j) { if(ancestor[ancl.first][j].first!=ancestor[ancr.first][j].first) { ancl = Operator::func_lca_edge_merge(ancestor[ancl.first][j],ancl); ancr = Operator::func_lca_edge_merge(ancestor[ancr.first][j],ancr); } } ancl = Operator::func_lca_edge_merge(ancestor[ancl.first][0],ancl); ancr = Operator::func_lca_edge_merge(ancestor[ancr.first][0],ancr); return Operator::func_lca_edge_merge(ancl,ancr); } pair<TypeEdge,vector<size_t>> diameter_impl() { StaticTree tree = StaticTree::builder(g).build(); size_t root = 0; { tree.make_root(0); } root = max_element(tree.edge_dist.begin(),tree.edge_dist.end()) - tree.edge_dist.begin(); { tree.make_root(root); } size_t leaf = max_element(tree.edge_dist.begin(),tree.edge_dist.end()) - tree.edge_dist.begin(); TypeEdge sz = tree.edge_dist[leaf]; vector<size_t> st; { tree.make_parent(); while(leaf != root) { st.push_back(leaf); leaf = tree.parent[leaf].first; } st.push_back(root); } return make_pair(sz,st); } template<class TypeReroot> vector<TypeReroot> rerooting_impl(vector<TypeReroot> rerootdp,vector<TypeReroot> rerootparent) { for(size_t pa:order) for(auto& e:child[pa]) rerootdp[pa] = Operator::func_reroot_dp(rerootdp[pa],rerootdp[e.first]); for(size_t pa:reorder) { if(depth[pa]) rerootdp[pa] = Operator::func_reroot_dp(rerootdp[pa],rerootparent[pa]); size_t m = child[pa].size(); for(int j = 0; j < m && depth[pa]; ++j){ size_t ch = child[pa][j].first; rerootparent[ch] = Operator::func_reroot_dp(rerootparent[ch],rerootparent[pa]); } if(m <= 1) continue; vector<TypeReroot> l(m),r(m); for(int j = 0; j < m; ++j) { size_t ch = child[pa][j].first; l[j] = rerootdp[ch]; r[j] = rerootdp[ch]; } for(int j = 1; j+1 < m; ++j) l[j] = Operator::func_reroot_merge(l[j],l[j-1]); for(int j = m-2; 0 <=j; --j) r[j] = Operator::func_reroot_merge(r[j],r[j+1]); size_t chl = child[pa].front().first; size_t chr = child[pa].back().first; rerootparent[chl] = Operator::func_reroot_dp(rerootparent[chl],r[1]); rerootparent[chr] = Operator::func_reroot_dp(rerootparent[chr],l[m-2]); for(int j = 1; j+1 < m; ++j) { size_t ch = child[pa][j].first; rerootparent[ch] = Operator::func_reroot_dp(rerootparent[ch],l[j-1]); rerootparent[ch] = Operator::func_reroot_dp(rerootparent[ch],r[j+1]); } } return rerootdp; } void make_eulertour() { dfs(reorder.front()); eulertour_range.resize(num); for(int i = 0; i < eulertour.size(); ++i) eulertour_range[eulertour[i]].second = i+1; for(int i = eulertour.size()-1; 0 <= i; --i) eulertour_range[eulertour[i]].first = i; } void make_heavy_light_decomposition(){ head.resize(num); hld.resize(num); iota(head.begin(),head.end(),0); for(size_t& pa:reorder) { pair<size_t,size_t> maxi = {0,num}; for(auto& p:child[pa]) maxi = max(maxi,{subtree_size[p.first],p.first}); if(maxi.first) head[maxi.second] = head[pa]; } stack<size_t> st_head,st_sub; size_t cnt = 0; //根に近い方から探索 for(size_t& root:reorder){ if(depth[root]) continue; //根をpush st_head.push(root); while(st_head.size()){ size_t h = st_head.top(); st_head.pop(); //部分木の根をpush st_sub.push(h); while (st_sub.size()){ size_t pa = st_sub.top(); st_sub.pop(); //部分木をカウントしていく hld[pa] = cnt++; //子を探索 for(auto& p:child[pa]) { //子のheadが親と同じなら、そのまま進む if(head[p.first]==head[pa]) st_sub.push(p.first); //そうじゃない場合は、そこから新しく部分木としてみなす else st_head.push(p.first); } } } } } //type 0: vertex, 1: edge vector<pair<size_t,size_t>> path_impl(size_t u,size_t v,int type = 0) { vector<pair<size_t,size_t>> path; while(1){ if(hld[u]>hld[v]) swap(u,v); if(head[u]!=head[v]) { path.push_back({hld[head[v]],hld[v]}); v=parent[head[v]].first; } else { path.push_back({hld[u],hld[v]}); break; } } reverse(path.begin(),path.end()); if(type) path.front().first++; return path; } pair<vector<pair<size_t,size_t>>,vector<pair<size_t,size_t>>> ordered_path_impl(size_t u,size_t v,int type = 0) { vector<pair<size_t,size_t>> path_lca_to_u; vector<pair<size_t,size_t>> path_lca_to_v; while(1){ if(head[u] == head[v]) { if(depth[u] < depth[v]) path_lca_to_v.emplace_back(hld[u]+type,hld[v]); else path_lca_to_u.emplace_back(hld[v]+type,hld[u]); break; } else if(hld[u] < hld[v]) { path_lca_to_v.emplace_back(hld[head[v]],hld[v]); v = parent[head[v]].first; } else if(hld[u] > hld[v]) { path_lca_to_u.emplace_back(hld[head[u]],hld[u]); u = parent[head[u]].first; } } reverse(path_lca_to_v.begin(),path_lca_to_v.end()); return {path_lca_to_u,path_lca_to_v}; } size_t lca_idx_impl(size_t u,size_t v){ while(1){ if(hld[u]>hld[v]) swap(u,v); if(head[u]==head[v]) return u; v=parent[head[v]].first; } } vector<size_t> head; public: vector<size_t> depth; vector<size_t> order; vector<size_t> reorder; vector<size_t> subtree_size; vector<pair<size_t,TypeEdge>> parent; vector<vector<pair<size_t,TypeEdge>>> child; vector<TypeEdge> edge_dist; vector<array<pair<size_t,TypeEdge>,Operator::bit>> ancestor; vector<size_t> eulertour; vector<pair<size_t,size_t>> eulertour_range; vector<size_t> hld; /** * O(N) builder */ static StaticTreeBuilder<Operator> builder(Graph<TypeEdge>& graph) { return StaticTreeBuilder<Operator>(graph);} /** * O(logN) after make_ancestor * return {lca,lca_dist} l and r must be connected */ pair<size_t,TypeEdge> lca(size_t l, size_t r) {return lca_impl(l,r);} /** * O(N) anytime * return {diameter size,diameter set} */ pair<TypeEdge,vector<size_t>> diameter(void){return diameter_impl();} /** * O(N) after make_child */ template<class TypeReroot> vector<TypeReroot> rerooting(const vector<TypeReroot>& rerootdp,const vector<TypeReroot>& rerootparent) {return rerooting_impl(rerootdp,rerootparent);} /** * O(logN) */ vector<pair<size_t,size_t>> vertex_set_on_path(size_t u, size_t v) {return path_impl(u,v,0);} /** /** * O(logN) */ vector<pair<size_t,size_t>> edge_set_on_path(size_t u, size_t v) {return path_impl(u,v,1);} /** * O(logN) * {lca to u path,lca to v path} */ pair<vector<pair<size_t,size_t>>,vector<pair<size_t,size_t>>> vertex_ordered_set_on_path(size_t u, size_t v) {return ordered_path_impl(u,v,0);} /** * O(logN) * {lca to u path,lca to v path} */ pair<vector<pair<size_t,size_t>>,vector<pair<size_t,size_t>>> edge_ordered_set_on_path(size_t u, size_t v) {return ordered_path_impl(u,v,1);} /** * O(logN) ancestorのlcaより定数倍軽め。idxだけ */ size_t lca_idx(size_t u, size_t v) {return lca_idx_impl(u,v);} }; template<class Operator> class StaticTreeBuilder { bool is_root_made =false; bool is_child_made =false; bool is_parent_made=false; bool is_subtree_size_made=false; public: using TypeEdge = typename Operator::TypeEdge; StaticTreeBuilder(Graph<TypeEdge>& g):tree(g){} StaticTreeBuilder& root(const int rt) { is_root_made=true; tree.make_root(rt); return *this;} StaticTreeBuilder& root() { is_root_made=true; tree.make_root(); return *this;} StaticTreeBuilder& child() { assert(is_root_made); is_child_made=true; tree.make_child(); return *this;} StaticTreeBuilder& parent() { assert(is_root_made); is_parent_made=true; tree.make_parent(); return *this;} StaticTreeBuilder& subtree_size() { assert(is_child_made); is_subtree_size_made=true; tree.make_subtree_size(); return *this;} StaticTreeBuilder& ancestor() { assert(is_parent_made); tree.make_ancestor(); return *this;} StaticTreeBuilder& eulertour() { assert(is_child_made); tree.make_eulertour(); return *this;} StaticTreeBuilder& heavy_light_decomposition() { assert(is_subtree_size_made); assert(is_parent_made); tree.make_heavy_light_decomposition(); return *this;} StaticTree<Operator>&& build() {return move(tree);} private: StaticTree<Operator> tree; }; template<class T> struct StaticTreeOperator{ using TypeEdge = T; inline static constexpr size_t bit = 20; inline static constexpr TypeEdge unit_edge = 0; inline static constexpr TypeEdge unit_lca_edge = 0; inline static constexpr TypeEdge func_edge_merge(const TypeEdge& parent,const TypeEdge& w){return parent+w;} inline static constexpr pair<size_t,TypeEdge> func_lca_edge_merge(const pair<size_t,TypeEdge>& l,const pair<size_t,TypeEdge>& r){return make_pair(l.first,l.second+r.second);} template<class TypeReroot> inline static constexpr TypeReroot func_reroot_dp(const TypeReroot& l,const TypeReroot& r) {return {l.first+r.first+r.second,l.second+r.second};} template<class TypeReroot> inline static constexpr TypeReroot func_reroot_merge(const TypeReroot& l,const TypeReroot& r) {return {l.first+r.first,l.second+r.second};} }; //auto tree = StaticTree<StaticTreeOperator<int>>::builder(g).build(); #line 1 "lib/00-util/ModInt.cpp" /* * @title ModInt * @docs md/util/ModInt.md */ template<long long mod> class ModInt { public: long long x; constexpr ModInt():x(0) {} constexpr ModInt(long long y) : x(y>=0?(y%mod): (mod - (-y)%mod)%mod) {} constexpr ModInt &operator+=(const ModInt &p) {if((x += p.x) >= mod) x -= mod;return *this;} constexpr ModInt &operator+=(const long long y) {ModInt p(y);if((x += p.x) >= mod) x -= mod;return *this;} constexpr ModInt &operator+=(const int y) {ModInt p(y);if((x += p.x) >= mod) x -= mod;return *this;} constexpr ModInt &operator-=(const ModInt &p) {if((x += mod - p.x) >= mod) x -= mod;return *this;} constexpr ModInt &operator-=(const long long y) {ModInt p(y);if((x += mod - p.x) >= mod) x -= mod;return *this;} constexpr ModInt &operator-=(const int y) {ModInt p(y);if((x += mod - p.x) >= mod) x -= mod;return *this;} constexpr ModInt &operator*=(const ModInt &p) {x = (x * p.x % mod);return *this;} constexpr ModInt &operator*=(const long long y) {ModInt p(y);x = (x * p.x % mod);return *this;} constexpr ModInt &operator*=(const int y) {ModInt p(y);x = (x * p.x % mod);return *this;} constexpr ModInt &operator^=(const ModInt &p) {x = (x ^ p.x) % mod;return *this;} constexpr ModInt &operator^=(const long long y) {ModInt p(y);x = (x ^ p.x) % mod;return *this;} constexpr ModInt &operator^=(const int y) {ModInt p(y);x = (x ^ p.x) % mod;return *this;} constexpr ModInt &operator/=(const ModInt &p) {*this *= p.inv();return *this;} constexpr ModInt &operator/=(const long long y) {ModInt p(y);*this *= p.inv();return *this;} constexpr ModInt &operator/=(const int y) {ModInt p(y);*this *= p.inv();return *this;} constexpr ModInt operator=(const int y) {ModInt p(y);*this = p;return *this;} constexpr ModInt operator=(const long long y) {ModInt p(y);*this = p;return *this;} constexpr ModInt operator-() const {return ModInt(-x); } constexpr ModInt operator++() {x++;if(x>=mod) x-=mod;return *this;} constexpr ModInt operator--() {x--;if(x<0) x+=mod;return *this;} constexpr ModInt operator+(const ModInt &p) const { return ModInt(*this) += p; } constexpr ModInt operator-(const ModInt &p) const { return ModInt(*this) -= p; } constexpr ModInt operator*(const ModInt &p) const { return ModInt(*this) *= p; } constexpr ModInt operator/(const ModInt &p) const { return ModInt(*this) /= p; } constexpr ModInt operator^(const ModInt &p) const { return ModInt(*this) ^= p; } constexpr bool operator==(const ModInt &p) const { return x == p.x; } constexpr bool operator!=(const ModInt &p) const { return x != p.x; } // ModInt inv() const {int a=x,b=mod,u=1,v=0,t;while(b > 0) {t = a / b;swap(a -= t * b, b);swap(u -= t * v, v);} return ModInt(u);} constexpr ModInt inv() const {int a=x,b=mod,u=1,v=0,t=0,tmp=0;while(b > 0) {t = a / b;a-=t*b;tmp=a;a=b;b=tmp;u-=t*v;tmp=u;u=v;v=tmp;} return ModInt(u);} constexpr ModInt pow(long long n) const {ModInt ret(1), mul(x);for(;n > 0;mul *= mul,n >>= 1) if(n & 1) ret *= mul;return ret;} friend ostream &operator<<(ostream &os, const ModInt &p) {return os << p.x;} friend istream &operator>>(istream &is, ModInt &a) {long long t;is >> t;a = ModInt<mod>(t);return (is);} }; constexpr long long MOD_998244353 = 998244353; constexpr long long MOD_1000000007 = 1'000'000'000LL + 7; //' #line 1 "lib/10-segment-tree/SegmentTree.cpp" /* * @title SegmentTree - 非再帰抽象化セグメント木 * @docs md/segment-tree/SegmentTree.md */ template<class Monoid> class SegmentTree { using TypeNode = typename Monoid::TypeNode; size_t length; size_t num; vector<TypeNode> node; vector<pair<int,int>> range; inline void build() { for (int i = length - 1; i >= 0; --i) node[i] = Monoid::func_fold(node[(i<<1)+0],node[(i<<1)+1]); range.resize(2 * length); for (int i = 0; i < length; ++i) range[i+length] = make_pair(i,i+1); for (int i = length - 1; i >= 0; --i) range[i] = make_pair(range[(i<<1)+0].first,range[(i<<1)+1].second); } public: //unitで初期化 SegmentTree(const size_t num): num(num) { for (length = 1; length <= num; length *= 2); node.resize(2 * length, Monoid::unit_node); build(); } //vectorで初期化 SegmentTree(const vector<TypeNode> & vec) : num(vec.size()) { for (length = 1; length <= vec.size(); length *= 2); node.resize(2 * length, Monoid::unit_node); for (int i = 0; i < vec.size(); ++i) node[i + length] = vec[i]; build(); } //同じinitで初期化 SegmentTree(const size_t num, const TypeNode init) : num(num) { for (length = 1; length <= num; length *= 2); node.resize(2 * length, Monoid::unit_node); for (int i = 0; i < length; ++i) node[i+length] = init; build(); } //[idx,idx+1) void operate(size_t idx, const TypeNode var) { if(idx < 0 || length <= idx) return; idx += length; node[idx] = Monoid::func_operate(node[idx],var); while(idx >>= 1) node[idx] = Monoid::func_fold(node[(idx<<1)+0],node[(idx<<1)+1]); } //[l,r) TypeNode fold(int l, int r) { if (l < 0 || length <= l || r < 0 || length < r) return Monoid::unit_node; TypeNode vl = Monoid::unit_node, vr = Monoid::unit_node; for(l += length, r += length; l < r; l >>=1, r >>=1) { if(l&1) vl = Monoid::func_fold(vl,node[l++]); if(r&1) vr = Monoid::func_fold(node[--r],vr); } return Monoid::func_fold(vl,vr); } //range[l,r) return [l,r] search max right int prefix_binary_search(int l, int r, TypeNode var) { assert(0 <= l && l < length && 0 < r && r <= length); TypeNode ret = Monoid::unit_node; size_t off = l; for(size_t idx = l+length; idx < 2*length && off < r; ){ if(range[idx].second<=r && !Monoid::func_check(Monoid::func_fold(ret,node[idx]),var)) { ret = Monoid::func_fold(ret,node[idx]); off = range[idx++].second; if(!(idx&1)) idx >>= 1; } else{ idx <<=1; } } return off; } //range(l,r] return [l,r] search max left int suffix_binary_search(const int l, const int r, const TypeNode var) { assert(-1 <= l && l < (int)length-1 && 0 <= r && r < length); TypeNode ret = Monoid::unit_node; int off = r; for(size_t idx = r+length; idx < 2*length && l < off; ){ if(l < range[idx].first && !Monoid::func_check(Monoid::func_fold(node[idx],ret),var)) { ret = Monoid::func_fold(node[idx],ret); off = range[idx--].first-1; if(idx&1) idx >>= 1; } else{ idx = (idx<<1)+1; } } return off; } void print(){ // cout << "node" << endl; // for(int i = 1,j = 1; i < 2*length; ++i) { // cout << node[i] << " "; // if(i==((1<<j)-1) && ++j) cout << endl; // } cout << "vector" << endl; cout << "{ " << fold(0,1); for(int i = 1; i < length; ++i) cout << ", " << fold(i,i+1); cout << " }" << endl; } }; #line 1 "lib/99-operator/monoid/MonoidRangeCompositePointUpdate.cpp" /* * @title MonoidRangeCompositePointUpdate - [区間一次関数, 点更新] * @docs md/operator/monoid/MonoidRangeCompositePointUpdate.md */ template<class T> struct MonoidRangeCompositePointUpdate { using TypeNode = T; inline static constexpr TypeNode unit_node = make_pair(1,0); inline static constexpr TypeNode func_fold(TypeNode l,TypeNode r){return {r.first*l.first,r.first*l.second+r.second};} inline static constexpr TypeNode func_operate(TypeNode l,TypeNode r){return r;} inline static constexpr bool func_check(TypeNode nodeVal,TypeNode var){return var == nodeVal;} }; #line 17 "test/graph/Tree-hld-vertex-3.test.cpp" //一次関数 template<class T> struct MonoidRangeRevCompositePointUpdate { using TypeNode = T; inline static constexpr TypeNode unit_node = make_pair(1,0); inline static constexpr TypeNode func_fold(TypeNode l,TypeNode r){return {l.first*r.first,l.first*r.second+l.second};} inline static constexpr TypeNode func_operate(TypeNode l,TypeNode r){return r;} inline static constexpr bool func_check(TypeNode nodeVal,TypeNode var){return var == nodeVal;} }; using modint = ModInt<998244353>; int main(void){ cin.tie(0);ios::sync_with_stdio(false); int N,Q; cin >> N >> Q; SegmentTree<MonoidRangeCompositePointUpdate<pair<modint,modint>>> segLtoR(N,{1,0}); SegmentTree<MonoidRangeRevCompositePointUpdate<pair<modint,modint>>> segRtoL(N,{1,0}); vector<int> A(N),B(N); for(int i=0;i<N;++i) cin >> A[i] >> B[i]; Graph<int> g(N); for(int i=0;i+1<N;++i) { int u,v; cin >> u >> v; g.make_bidirectional_edge(u,v,1); } auto tree = StaticTree<StaticTreeOperator<int>>::builder(g).root(0).parent().child().subtree_size().heavy_light_decomposition().build(); for(int i=0;i<N;++i) { int j = tree.hld[i]; segLtoR.operate(j,{A[i],B[i]}); segRtoL.operate(j,{A[i],B[i]}); } while(Q--) { int q; cin >> q; if(q==0) { int i,a,b; cin >> i >> a >> b; int j = tree.hld[i]; segLtoR.operate(j,{a,b}); segRtoL.operate(j,{a,b}); } else { int l,r,x; cin >> l >> r >> x; auto tp = tree.vertex_ordered_set_on_path(l,r); pair<modint,modint> line = {1,0}; for(auto& p:tp.first) { auto tmp = segRtoL.fold(p.first,p.second+1); line = {tmp.first*line.first,tmp.first*line.second+tmp.second}; } for(auto& p:tp.second) { auto tmp = segLtoR.fold(p.first,p.second+1); line = {tmp.first*line.first,tmp.first*line.second+tmp.second}; } cout << line.first*x+line.second << "\n"; } } return 0; }