cp-library

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

View the Project on GitHub Hoshinonono/cp-library

:heavy_check_mark: Test/Library Checker/Tree/vertex_set_path_composite01.test.cpp

Depends on

Code

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

#include <bits/stdc++.h>

#include "Tree/hld.hpp"

#include "DataStructure/segtree.hpp"

#include "Math/modint.hpp"


//using mint = prime_modint<1000000007>;

using mint = prime_modint<998244353>;

using namespace std;

using S = pair<mint, mint>;
S op1(S lhs, S rhs){
    return {rhs.first * lhs.first, rhs.first * lhs.second + rhs.second};
}
S op2(S lhs, S rhs){
    return {lhs.first * rhs.first, lhs.first * rhs.second + lhs.second};
}
S e(){
    return make_pair(1, 0);
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int N, Q, cmd, u, v, x;
    cin >> N >> Q;
    vector<pair<mint,mint>> a(N), b(N);
    vector<vector<int>> g(N);
    for(int i = 0; i < N; i++){
        cin >> a[i].first.v >> a[i].second.v;
    }
    for(int i = 1; i < N; i++){
        cin >> u >> v;
        g[u].emplace_back(v);
        g[v].emplace_back(u);
    }

    Heavy_Light_Decomposition HLD(g);

    for(int i = 0; i < N; i++){
        b[HLD[i]] = a[i];
    }
    segtree<S, op1, e> seg1(b);
    segtree<S, op2, e> seg2(b);

    auto qf = [&](int l, int r){
        return seg1.prod(l, r);
    };
    auto rev_qf = [&](int l, int r){
        return seg2.prod(l, r);
    };
    auto f = [&](S lhs, S rhs){
        return make_pair(rhs.first * lhs.first, rhs.first * lhs.second + rhs.second);
    };

    while(Q--){
        cin >> cmd >> u >> v >> x;
        if(cmd == 0){
            seg1.set(HLD[u], make_pair(v, x));
            seg2.set(HLD[u], make_pair(v, x));
        }else{
            auto pa = HLD.noncom_query(u, v, e(), qf, rev_qf, f);
            cout << pa.first * x + pa.second << '\n';
        }
    }
}
#line 1 "Test/Library Checker/Tree/vertex_set_path_composite01.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/vertex_set_path_composite"

#include <bits/stdc++.h>

#line 1 "Tree/hld.hpp"
struct Heavy_Light_Decomposition{
    int N, tim = 0;
    std::vector<int> sz, ent, leader, order, par;
    std::vector<std::vector<int>> &G;
    Heavy_Light_Decomposition(std::vector<std::vector<int>> &g) : 
            N(g.size()), G(g), sz(N), ent(N), leader(N), order(N), par(N) {
        dfs_size(0, -1);
        dfs_hld(0);
    }
    const int operator[](int v) const {
        assert(0 <= v && v < N);
        return ent[v];
    }
    int operator[](int v) { 
        assert(0 <= v && v < N);
        return ent[v];
    }
    int la(int v, int k) {
        while(true) {
            int u = leader[v];
            if(ent[v] - k >= ent[u]) return order[ent[v] - k];
            k -= ent[v] - ent[u] + 1;
            v = par[u];
        }
    }
    int la(int from, int to, int d){
        int d1 = 0, d2 = 0;
        int v = from, u = to;
        do{
            if(ent[u] < ent[v]){
                if(leader[u] == leader[v]){
                    d1 += ent[v] - ent[u];
                    break;
                }
                d1 += ent[v] - ent[leader[v]] + 1;
                v = par[leader[v]];
            }else{
                if(leader[u] == leader[v]){
                    d2 += ent[u] - ent[v];
                    break;
                }
                d2 += ent[u] - ent[leader[u]] + 1;
                u = par[leader[u]];
            }
        }while(true);
        if(d > d1 + d2) return -1;
        return d <= d1 ? la(from, d) : la(to, d1 + d2 - d);
    }
    int lca(int u, int v) {
        do{
            if(ent[u] > ent[v]) std::swap(u, v);
            if(leader[u] == leader[v]) return u;
            v = par[leader[v]];
        }while(true);
    }
    int dist(int u, int v){
        int ans = 0;
        do{
            if(ent[u] > ent[v]) std::swap(u, v);
            if(leader[u] == leader[v]) return ans + ent[v] - ent[u];
            ans += ent[v] - ent[leader[v]] + 1;
            v = par[leader[v]];
        }while(true);
    }
    template< typename T, typename Q, typename F >
    T query(int u, int v, const T &identity, const Q &qf, const F &f, bool edge = false) {
        T ans = identity;
        do{
            if(ent[u] > ent[v]) std::swap(u, v);
            if(leader[u] == leader[v]) break;
            ans = f( qf(ent[leader[v]], ent[v] + 1), ans);
            v = par[leader[v]];
        }while(true);
        return f( qf(ent[u] + edge, ent[v] + 1), ans);
    }
    template< typename T, typename Q1, typename Q2, typename F >
    T noncom_query(int u, int v, const T &identity, 
                   const Q1 &qf, const Q2 &rev_qf, const F &f, bool edge = false) {
        T sml = identity, smr = identity;
        do{
            if(leader[u] == leader[v]) break;
            if(ent[u] < ent[v]){
                smr = f( qf(ent[leader[v]], ent[v] + 1), smr);
                v = par[leader[v]];
            }else{
                sml = f( sml, rev_qf(ent[leader[u]], ent[u] + 1));
                u = par[leader[u]];
            }
        }while(true);
        if(ent[u] < ent[v]){
            return f(sml,  f( qf(ent[u] + edge, ent[v] + 1), smr));
        }else{
            return f(f(sml, rev_qf(ent[v] + edge, ent[u] + 1)), smr);
        }
    }
    template< typename Q >
    void update(int u, int v, const Q &q, bool edge = false) {
        do{
            if(ent[u] > ent[v]) std::swap(u, v);
            if(leader[u] == leader[v]) break;
            q(ent[leader[v]], ent[v] + 1);
            v = par[leader[v]];
        }while(true);
        q(ent[u] + edge, ent[v] + 1);
    }
    private:
    void dfs_size(int v, int p){
        par[v] = p;
        sz[v] = 1;
        if(!G[v].empty() && G[v][0] == p) std::swap(G[v][0], G[v].back());
        for(auto &u : G[v]){
            if(u == p) continue;
            dfs_size(u, v);
            sz[v] += sz[u];
            if(sz[u] > sz[G[v][0]]) std::swap(G[v][0], u);
        }
    }
    void dfs_hld(int v){
        ent[v] = tim++;
        order[ent[v]] = v;
        for(auto &u : G[v]) {
            if(u == par[v]) continue;
            leader[u] = (G[v][0] == u ? leader[v] : u);
            dfs_hld(u);
        }
    }
};
#line 1 "DataStructure/segtree.hpp"
template <class S, S (*op)(S, S), S (*e)()> struct segtree {
    public:
    segtree() : segtree(0) {}
    segtree(int n) : segtree(std::vector<S>(n, e())) {}
    segtree(const std::vector<S>& v) : _n(int(v.size())) {
        log = 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) {
        assert(0 <= p && p < _n);
        return d[p + size];
    }
    const S operator[](int p) const { return get(p); }
    S operator[](int p) { return get(p); }

    S prod(int l, int r) {
        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() { return d[1]; }

    template <bool (*f)(S)> int max_right(int l) {
        return max_right(l, [](S x) { return f(x); });
    }
    template <class F> int max_right(int l, F f) {
        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) {
        return min_left(r, [](S x) { return f(x); });
    }
    template <class F> int min_left(int r, F f) {
        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;
    int ceil_pow2(int n) {
        int x = 0;
        while ((1U << x) < (unsigned int)(n)) x++;
        return x;
    }
    void update(int k) { d[k] = op(d[2 * k], d[2 * k + 1]); }
};
#line 1 "Math/modint.hpp"
template<const unsigned int MOD> struct prime_modint {
    using mint = prime_modint;
    unsigned int v;
    prime_modint() : v(0) {}
    prime_modint(unsigned int a) { a %= MOD; v = a; }
    prime_modint(unsigned long long a) { a %= MOD; v = a; }
    prime_modint(int a) { a %= (int)(MOD); if(a < 0)a += MOD; v = a; }
    prime_modint(long long a) { a %= (int)(MOD); if(a < 0)a += MOD; v = a; }
    static constexpr int mod() { return MOD; }
    mint& operator++() {v++; if(v == MOD)v = 0; return *this;}
    mint& operator--() {if(v == 0)v = MOD; v--; return *this;}
    mint operator++(int) { mint result = *this; ++*this; return result; }
    mint operator--(int) { mint result = *this; --*this; return result; }
    mint& operator+=(const mint& rhs) { v += rhs.v; if(v >= MOD) v -= MOD; return *this; }
    mint& operator-=(const mint& rhs) { if(v < rhs.v) v += MOD; v -= rhs.v; return *this; }
    mint& operator*=(const mint& rhs) {
        v = (unsigned int)((unsigned long long)(v) * rhs.v % MOD);
        return *this;
    }
    mint& operator/=(const mint& rhs) { return *this = *this * rhs.inv(); }
    mint operator+() const { return *this; }
    mint operator-() const { return mint() - *this; }
    mint pow(long long n) const {
        assert(0 <= n);
        mint r = 1, x = *this;
        while (n) {
            if (n & 1) r *= x;
            x *= x;
            n >>= 1;
        }
        return r;
    }
    mint inv() const { assert(v); return pow(MOD - 2); }
    friend mint operator+(const mint& lhs, const mint& rhs) { return mint(lhs) += rhs; }
    friend mint operator-(const mint& lhs, const mint& rhs) { return mint(lhs) -= rhs; }
    friend mint operator*(const mint& lhs, const mint& rhs) { return mint(lhs) *= rhs; }
    friend mint operator/(const mint& lhs, const mint& rhs) { return mint(lhs) /= rhs; }
    friend bool operator==(const mint& lhs, const mint& rhs) { return (lhs.v == rhs.v); }
    friend bool operator!=(const mint& lhs, const mint& rhs) { return (lhs.v != rhs.v); }
    friend std::ostream& operator << (std::ostream &os, const mint& rhs) noexcept { return os << rhs.v; }
};
#line 7 "Test/Library Checker/Tree/vertex_set_path_composite01.test.cpp"

//using mint = prime_modint<1000000007>;

using mint = prime_modint<998244353>;

using namespace std;

using S = pair<mint, mint>;
S op1(S lhs, S rhs){
    return {rhs.first * lhs.first, rhs.first * lhs.second + rhs.second};
}
S op2(S lhs, S rhs){
    return {lhs.first * rhs.first, lhs.first * rhs.second + lhs.second};
}
S e(){
    return make_pair(1, 0);
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int N, Q, cmd, u, v, x;
    cin >> N >> Q;
    vector<pair<mint,mint>> a(N), b(N);
    vector<vector<int>> g(N);
    for(int i = 0; i < N; i++){
        cin >> a[i].first.v >> a[i].second.v;
    }
    for(int i = 1; i < N; i++){
        cin >> u >> v;
        g[u].emplace_back(v);
        g[v].emplace_back(u);
    }

    Heavy_Light_Decomposition HLD(g);

    for(int i = 0; i < N; i++){
        b[HLD[i]] = a[i];
    }
    segtree<S, op1, e> seg1(b);
    segtree<S, op2, e> seg2(b);

    auto qf = [&](int l, int r){
        return seg1.prod(l, r);
    };
    auto rev_qf = [&](int l, int r){
        return seg2.prod(l, r);
    };
    auto f = [&](S lhs, S rhs){
        return make_pair(rhs.first * lhs.first, rhs.first * lhs.second + rhs.second);
    };

    while(Q--){
        cin >> cmd >> u >> v >> x;
        if(cmd == 0){
            seg1.set(HLD[u], make_pair(v, x));
            seg2.set(HLD[u], make_pair(v, x));
        }else{
            auto pa = HLD.noncom_query(u, v, e(), qf, rev_qf, f);
            cout << pa.first * x + pa.second << '\n';
        }
    }
}
Back to top page