Algorithm-Library

This documentation is automatically generated by online-judge-tools/verification-helper

View the Project on GitHub UScuber/Algorithm-Library

:heavy_check_mark: test/yosupo/Data-Structure/Vertex-Set-Path-Composite.test.cpp

Depends on

Code

#define PROBLEM "https://judge.yosupo.jp/problem/vertex_set_path_composite"

#include "../../../template/template.hpp"

#include "../../../data-structure/HLD.hpp"
#include "../../../math/mint.hpp"
#include "../../../others/fastIO.hpp"

using mint = Mint<998244353>;

struct Data {
  mint a,b;
};
Data e(){
  return { 1, 0 };
}
Data op(const Data &l, const Data &m){
  return { l.a*m.a, l.b*m.a + m.b };
}
Data rev_op(const Data &l, const Data &m){
  return { m.a*l.a, m.b*l.a + l.b };
}

int main(){
  int n,q;
  cin >> n >> q;
  vi a(n), b(n);
  rep(i, n) cin >> a[i] >> b[i];
  graph root(n);
  rep(i, n - 1){
    int a,b;
    cin >> a >> b;
    root[a].push_back(b);
    root[b].push_back(a);
  }
  HLD<Data,op,rev_op,e> hld(root);
  rep(i, n) hld.set(i, { a[i], b[i] });
  hld.build();
  int t,p,c,d,u,v,x;
  rep(_, q){
    cin >> t;
    if(t == 0){
      cin >> p >> c >> d;
      hld.update(p, { c, d });
    }else{
      cin >> u >> v >> x;
      const Data res = hld.query(u, v);
      const mint ans = res.a * x + res.b;
      cout << ans.x << '\n';
    }
  }
}
#line 1 "test/yosupo/Data-Structure/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 <cmath>
#include <string>
#include <vector>
#include <algorithm>
#include <tuple>
#include <cstdint>
#include <cstdio>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <deque>
#include <bitset>
#include <cctype>
#include <climits>
#include <functional>
#include <cassert>
#include <numeric>
#include <cstring>
#define rep(i, n) for(int i = 0; i < (n); i++)
#define per(i, n) for(int i = (n) - 1; i >= 0; i--)
using ll = long long;
#define vi vector<int>
#define vvi vector<vi>
#define vl vector<ll>
#define pii pair<int, int>
#define pll pair<ll, ll>
#define all(a) (a).begin(), (a).end()
#define rall(a) (a).rbegin(), (a).rend()
constexpr int mod = 1000000007;
using namespace std;
template<class T, class U>
bool chmax(T &a, const U &b){ return a < b ? (a = b, 1) : 0; }
template<class T, class U>
bool chmin(T &a, const U &b){ return a > b ? (a = b, 1) : 0; }
#line 4 "test/yosupo/Data-Structure/Vertex-Set-Path-Composite.test.cpp"

#line 2 "graph/template.hpp"

/**
 * @brief Graph Template
*/
template <class T>
struct Edge {
  int from,to;
  T cost;
  int idx;
  Edge(){};
  Edge(int f, int t, T c=1, int i=-1) : from(f), to(t), cost(c), idx(i){}
  Edge(int t) : to(t), from(-1), cost(1), idx(-1){}
  operator int() const{ return to; }
  bool operator<(const Edge &e){ return cost < e.cost; }
};
template <class T>
struct Graph : vector<vector<Edge<T>>> {
  Graph(){}
  Graph(const int &n) : vector<vector<Edge<T>>>(n){}
  void add_edge(int a, int b, T c=1, int i=-1){
    (*this)[a].push_back({ a, b, c, i });
  }
};
using graph = Graph<int>;
#line 1 "SegmentTree/segtree.hpp"
template <class T, T(*op)(const T&,const T&), T(*e)()>
struct SegmentTree {
  SegmentTree(const int _n) : n(_n){
    while((1 << log) < n) log++;
    len = 1 << log;
    d.resize(len * 2, e());
  }
  void update(int k, const T &x){
    assert(0 <= k && k < n);
    k += len;
    d[k] = x;
    while(k > 1){
      k >>= 1;
      d[k] = op(d[k*2], d[k*2+1]);
    }
  }
  void set(const int i, const T &x){
    assert(0 <= i && i < n);
    d[i + len] = x;
  }
  T get(const int i) const{
    assert(0 <= i && i < n);
    return d[i + len];
  }
  void build(){
    for(int k = len - 1; k >= 1; k--)
      d[k] = op(d[2*k], d[2*k+1]);
  }
  T query(int l, int r){
    assert(0 <= l && l <= r && r <= n);
    l += len; r += len;
    T left = e(), right = e();
    while(l < r){
      if(l & 1) left = op(left, d[l++]);
      if(r & 1) right = op(d[--r], right);
      l >>= 1; r >>= 1;
    }
    return op(left, right);
  }
  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 += len;
    T sm = e();
    do {
      l /= l & -l;
      if(!f(op(sm, d[l]))){
        while(l < len){
          l <<= 1;
          if(f(op(sm, d[l]))){
            sm = op(sm, d[l]);
            l++;
          }
        }
        return l - len;
      }
      sm = op(sm, d[l]);
      l++;
    }while(l & (l - 1));
    return n;
  }
  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 += len;
    T sm = e();
    do {
      r /= r & -r;
      if(r > 1) r--;
      if(!f(op(d[r], sm))){
        while(r < len){
          r = r * 2 + 1;
          if(f(op(d[r], sm))){
            sm = op(d[r], sm);
            r--;
          }
        }
        return r + 1 - len;
      }
      sm = op(d[r], sm);
    }while(r & (r - 1));
    return 0;
  }
  private:
  int n = 1, log = 0, len = 0;
  vector<T> d;
};
#line 3 "data-structure/HLD.hpp"

template <class T, T(*op)(const T&,const T&), T(*rev_op)(const T&,const T&), T(*e)()>
struct HLD {
  graph root;
  int n, in_cnt = 0;
  vector<int> pre, sh, sz, p;
  SegmentTree<T,op,e> seg;
  SegmentTree<T,rev_op,e> rseg;
  HLD(const graph &g) : root(g), n(g.size()), pre(n), sh(n), sz(n), p(n), seg(n), rseg(n){
    size(0, -1);
    calc(0, -1, 0);
  }
  void size(int pos, int par){
    sz[pos] = 1;
    int mx = -1, idx = -1, cnt = -1;
    for(const int &x : root[pos]){
      cnt++;
      if(x == par) continue;
      size(x, pos);
      sz[pos] += sz[x];
      if(chmax(mx, sz[x])) idx = cnt;
    }
    if(idx != -1) swap(root[pos][0], root[pos][idx]);
  }
  void calc(int pos, int par, int v){
    p[pos] = in_cnt++;
    sh[pos] = v;
    pre[pos] = par;
    int cnt = -1;
    for(const int &x : root[pos]){
      cnt++;
      if(x == par) continue;
      if(cnt) calc(x, pos, x);
      else calc(x, pos, v);
    }
  }
  void set(int u, const T &x){
    seg.set(p[u], x);
    rseg.set(p[u], x);
  }
  void build(){
    seg.build();
    rseg.build();
  }

  void update(int u, const T &x){
    seg.update(p[u], x);
    rseg.update(p[u], x);
  }
  vector<pair<int,int>> query_path(int u, int v){
    vector<pair<int,int>> lef, rig;
    while(sh[u] != sh[v]){
      if(p[u] < p[v]){
        rig.emplace_back(p[sh[v]], p[v]);
        v = pre[sh[v]];
      }
      else{
        lef.emplace_back(p[u], p[sh[u]]);
        u = pre[sh[u]];
      }
    }
    if(p[u] < p[v]) rig.emplace_back(p[u], p[v]);
    else lef.emplace_back(p[u], p[v]);
    reverse(all(rig));
    lef.insert(lef.end(), all(rig));
    return lef;
  }
  T query(int u, int v){
    T res = e();
    for(const auto &x : query_path(u, v)){
      if(x.first <= x.second){
        res = op(res, seg.query(x.first, x.second+1));
      }else{
        res = op(res, rseg.query(x.second, x.first+1));
      }
    }
    return res;
  }
  T get(const int i){ return seg.get(p[i]); }
};
#line 2 "math/mint.hpp"

template <int mod>
struct Mint {
  ll x;
  constexpr Mint(ll x = 0) : x((x + mod) % mod){}
  static constexpr int get_mod(){ return mod; }
  constexpr Mint operator-() const{ return Mint(-x); }
  constexpr Mint operator+=(const Mint &a){
    if((x += a.x) >= mod) x -= mod;
    return *this;
  }
  constexpr Mint &operator++(){
    if(++x == mod) x = 0;
    return *this;
  }
  constexpr Mint operator++(int){
    Mint temp = *this;
    if(++x == mod) x = 0;
    return temp;
  }
  constexpr Mint &operator-=(const Mint &a){
    if((x -= a.x) < 0) x += mod;
    return *this;
  }
  constexpr Mint &operator--(){
    if(--x < 0) x += mod;
    return *this;
  }
  constexpr Mint operator--(int){
    Mint temp = *this;
    if(--x < 0) x += mod;
    return temp;
  }
  constexpr Mint &operator*=(const Mint &a){
    (x *= a.x) %= mod;
    return *this;
  }
  constexpr Mint operator+(const Mint &a) const{ return Mint(*this) += a; }
  constexpr Mint operator-(const Mint &a) const{ return Mint(*this) -= a; }
  constexpr Mint operator*(const Mint &a) const{ return Mint(*this) *= a; }
  constexpr Mint pow(ll t) const{
    if(!t) return 1;
    Mint res = 1, v = *this;
    while(t){
      if(t & 1) res *= v;
      v *= v;
      t >>= 1;
    }
    return res;
  }
  constexpr Mint inv() const{ return pow(mod - 2); }
  constexpr Mint &operator/=(const Mint &a){ return (*this) *= a.inv(); }
  constexpr Mint operator/(const Mint &a) const{ return Mint(*this) /= a; }
  constexpr bool operator==(const Mint &a) const{ return x == a.x; }
  constexpr bool operator!=(const Mint &a) const{ return x != a.x; }
  constexpr bool operator<(const Mint &a) const{ return x < a.x; }
  constexpr bool operator>(const Mint &a) const{ return x > a.x; }
  friend istream &operator>>(istream &is, Mint &a){ return is >> a.x; }
  friend ostream &operator<<(ostream &os, const Mint &a){ return os << a.x; }
};
//using mint = Mint<1000000007>;
#line 1 "others/fastIO.hpp"
namespace FastIO {
struct PreCalc {
  char num[10000 * 4];
  constexpr PreCalc() : num(){
    for(int i = 0; i < 10000; i++){
      int t = i;
      for(int j = 3; j >= 0; j--){
        num[i*4 + j] = (t % 10) + '0';
        t /= 10;
      }
    }
  }
};
static constexpr PreCalc pr;
struct FastIO {
  template <class T>
  using enable_if_integer = enable_if_t<is_integral<T>::value || is_same<T, __int128_t>::value || is_same<T, __uint128_t>::value>;
  static constexpr int buf_size = 1 << 20;
  static constexpr int rem = 1 << 6;
  char in_buf[buf_size], *in_cur = in_buf + buf_size;
  char out_buf[buf_size], *out_cur = out_buf;
  FastIO(){ load(); }
  ~FastIO(){ flush(); }
  void load(){
    const int len = in_buf + buf_size - in_cur;
    memmove(in_buf, in_cur, len);
    in_cur = in_buf;
    fread(in_buf + len, 1, buf_size - len, stdin);
  }
  void flush(){
    fwrite(out_buf, 1, out_cur - out_buf, stdout);
    out_cur = out_buf;
  }
  void through(){
    if(in_cur - in_buf >= buf_size - rem) load();
    while(*in_cur <= ' ') in_cur++;
    assert(in_buf <= in_cur && in_cur < in_buf + buf_size);
  }
  #define gc() (*in_cur++)
  template <class T, enable_if_integer<T>* = nullptr>
  inline void read(T &x){
    through();
    bool neg = false;
    int c = gc();
    if(c == '-') neg = true, c = gc();
    x = c^'0'; c = gc();
    while(c >= '0' && c <= '9') x = x*10 + (c^'0'), c = gc();
    if(neg) x = -x;
  }
  inline void read(string &x){
    through();
    x.clear();
    while(true){
      char *p = in_cur;
      while(*p > ' ' && p - in_buf < buf_size - rem) p++;
      copy(in_cur, p, back_inserter(x));
      in_cur = p;
      if(*p <= ' ') break;
      load();
    }
  }
  inline void read(char &x){
    through();
    x = gc();
  }
  #undef gc
  #define pc(c) *out_cur++ = (c)
  template <class T, enable_if_integer<T>* = nullptr>
  inline void out(T x){
    static constexpr int tmp_size = sizeof(T)*5/2;
    static char tmp[tmp_size];
    if(out_cur - out_buf >= buf_size - rem) flush();
    if(!x){ pc('0'); return; }
    if(x < 0){ pc('-'); x = -x; }
    int idx = tmp_size;
    while(x >= 10000){
      idx -= 4;
      memcpy(tmp + idx, pr.num + (x % 10000)*4, 4);
      x /= 10000;
    }
    if(x < 100){
      if(x < 10){
        pc(x + '0');
      }else{
        pc(x/10 + '0');
        pc(x%10 + '0');
      }
    }else{
      if(x < 1000){
        memcpy(out_cur, pr.num + x*4 + 1, 3);
        out_cur += 3;
      }else{
        memcpy(out_cur, pr.num + x*4, 4);
        out_cur += 4;
      }
    }
    memcpy(out_cur, tmp + idx, tmp_size - idx);
    out_cur += tmp_size - idx;
  }
  inline void out(const string &s){
    flush();
    fwrite(s.c_str(), 1, s.size(), stdout);
  }
  inline void out(const char c){
    if(out_cur - out_buf >= buf_size - rem) flush();
    pc(c);
  }
  #undef pc
  template <class T>
  friend FastIO &operator>>(FastIO &io, T &x){
    io.read(x);
    return io;
  }
  template <class T>
  friend FastIO &operator<<(FastIO &io, const T &x){
    io.out(x);
    return io;
  }
};
FastIO io;
} // namespace FastIO

using FastIO::io;
#define cin io
#define cout io
#line 8 "test/yosupo/Data-Structure/Vertex-Set-Path-Composite.test.cpp"

using mint = Mint<998244353>;

struct Data {
  mint a,b;
};
Data e(){
  return { 1, 0 };
}
Data op(const Data &l, const Data &m){
  return { l.a*m.a, l.b*m.a + m.b };
}
Data rev_op(const Data &l, const Data &m){
  return { m.a*l.a, m.b*l.a + l.b };
}

int main(){
  int n,q;
  cin >> n >> q;
  vi a(n), b(n);
  rep(i, n) cin >> a[i] >> b[i];
  graph root(n);
  rep(i, n - 1){
    int a,b;
    cin >> a >> b;
    root[a].push_back(b);
    root[b].push_back(a);
  }
  HLD<Data,op,rev_op,e> hld(root);
  rep(i, n) hld.set(i, { a[i], b[i] });
  hld.build();
  int t,p,c,d,u,v,x;
  rep(_, q){
    cin >> t;
    if(t == 0){
      cin >> p >> c >> d;
      hld.update(p, { c, d });
    }else{
      cin >> u >> v >> x;
      const Data res = hld.query(u, v);
      const mint ans = res.a * x + res.b;
      cout << ans.x << '\n';
    }
  }
}
Back to top page