library

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

View the Project on GitHub Harui-i/library

:heavy_check_mark: test/verify/yosupo-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 <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;
}
Back to top page