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);
  }

  HaruiLib::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();
      HaruiLib::Path path = hld.get_path(u,v);
      for (HaruiLib::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"
#include <type_traits>
#line 7 "math/modint.hpp"

template<int MOD, typename T = int>
struct static_modint {
    T value;

    constexpr explicit static_modint() : value(0) {}

    constexpr static_modint(long long v) {
        if constexpr (std::is_same<T, double>::value) {
            value = double(v);
        }
        else {
            value = int(((v % MOD) + MOD) % MOD);
        }
    }

    constexpr static_modint& operator+=(const static_modint& other) {
        if constexpr (std::is_same<T, double>::value) {
            value += other.value;
        }
        else {
            if ((value += other.value) >= MOD) value -= MOD;
        }
        return *this;
    }

    constexpr static_modint& operator-=(const static_modint& other) {
        if constexpr (std::is_same<T, double>::value) {
            value -= other.value;
        }
        else {
            if ((value -= other.value) < 0) value += MOD;
        }
        return *this;
    }

    constexpr static_modint& operator*=(const static_modint& other) {
        if constexpr (std::is_same<T, double>::value) {
            value *= other.value;
        }
        else {
            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 {
        if constexpr (std::is_same<T, double>::value) {
            static_modint ret;
            ret.value = double(1.0) / value;
            return ret;
        }
        else {
            int g, x, y;
            std::tie(g, x, y) = extendedGCD(value, MOD);
            assert(g == 1);
            if (x < 0) x += MOD;
            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();
    }

    T val() const {
        if constexpr (std::is_same<T, double>::value) {
            return double(value);
        }
        else 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 doublemodint = static_modint<59, double>;
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"

namespace HaruiLib {
  // 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>;
  
  /*
  木をいくつかのパスに分けるアルゴリズム。
  うまくDFSしてパスに分けると、同じパスの中でidが連続するので、一つのパスの中ではセグメント木などの列に対してのアルゴリズムが使えるようになる。
  
  頂点属性の問題はかんたん。
  辺属性の問題は、辺の子側の頂点にその情報をもたせて管理するといい。 そのときはLCAに注意する。
  */
  struct HLD {
  private:
    bool is_built = false;
  public:
    //vector<vector<int>>children;
    std::vector<int> parent;
    std::vector<int> id; // id[v] := 頂点vがdfs順で何番目にあるか。 HLDで分割したパスの中では、深さが浅い方から深い方へidが連続して増えていく。
    std::vector<int> id2;
    std::vector<int> head; // head[v] := 頂点vが所属する分割されたパスの、一番根に近い頂点。
    std::vector<int> depth; // depth[v] := 頂点vの深さ
    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);
      is_built = true;
    }
  
    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] = head[v]
        // そうでないなら、head[e.to] = e.to;
        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) {
      assert(is_built);
      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) {
      assert(is_built);
      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);
  }

  HaruiLib::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();
      HaruiLib::Path path = hld.get_path(u,v);
      for (HaruiLib::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