ACM_Notebook_new

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

View the Project on GitHub ngthanhtrung23/ACM_Notebook_new

:heavy_check_mark: DataStructure/test/link_cut_tree_vertexsetpathcomposite.test.cpp

Depends on

Code

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

#include <bits/stdc++.h>
using namespace std;

#include "../../Math/modint.h"
using modular = ModInt<998244353>;

#define PATH_QUERIES_ONLY
struct T {
    modular a, b;

    T() : a(1), b(0) {}
    T(modular _a, modular _b) : a(_a), b(_b) {}

    // return f(g())
    T operator + (const T& g) const {
        return T {
            a * g.a,
            a * g.b + b,
        };
    }

    T operator += (const T& g) {
        b = a * g.b + b;
        a = a * g.a;
        return *this;
    }
};
#include "../LinkCutTree.h"

#define FOR(i, a, b) for (int i = (a), _##i = (b); i <= _##i; ++i)
#define REP(i, a) for (int i = 0, _##i = (a); i < _##i; ++i)

int32_t main() {
    ios::sync_with_stdio(0); cin.tie(0);

    int n, q; cin >> n >> q;
    LinkCut tree(n);

    FOR(i,1,n) {
        modular a, b; cin >> a >> b;
        tree.set(i, T{a, b});
    }

    REP(i,n-1) {
        int u, v; cin >> u >> v;
        ++u; ++v;
        tree.link(u, v);
    }

    while (q--) {
        int typ; cin >> typ;
        if (typ == 0) {  // remove (u, v), add (w, x)
            int u, v, w, x; cin >> u >> v >> w >> x;
            ++u; ++v;
            ++w; ++x;
            tree.cut(u, v);
            tree.link(w, x);
        } else if (typ == 1) {  // set f(p) = cx + d
            int p; cin >> p;
            ++p;
            modular c, d; cin >> c >> d;
            tree.set(p, T{c, d});
        } else if (typ == 2) {  // get path (u, v) and apply f(x)
            int u, v; cin >> u >> v;
            ++u; ++v;
            modular x; cin >> x;

            auto f = tree.getPath(u, v);
            cout << f.a * x + f.b << '\n';
        }
    }
    return 0;
}
#line 1 "DataStructure/test/link_cut_tree_vertexsetpathcomposite.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/dynamic_tree_vertex_set_path_composite"

#include <bits/stdc++.h>
using namespace std;

#line 1 "Math/modint.h"
// ModInt {{{
template<int MD> struct ModInt {
    using ll = long long;
    int x;

    constexpr ModInt() : x(0) {}
    constexpr ModInt(ll v) { _set(v % MD + MD); }
    constexpr static int mod() { return MD; }
    constexpr explicit operator bool() const { return x != 0; }

    constexpr ModInt operator + (const ModInt& a) const {
        return ModInt()._set((ll) x + a.x);
    }
    constexpr ModInt operator - (const ModInt& a) const {
        return ModInt()._set((ll) x - a.x + MD);
    }
    constexpr ModInt operator * (const ModInt& a) const {
        return ModInt()._set((ll) x * a.x % MD);
    }
    constexpr ModInt operator / (const ModInt& a) const {
        return ModInt()._set((ll) x * a.inv().x % MD);
    }
    constexpr ModInt operator - () const {
        return ModInt()._set(MD - x);
    }

    constexpr ModInt& operator += (const ModInt& a) { return *this = *this + a; }
    constexpr ModInt& operator -= (const ModInt& a) { return *this = *this - a; }
    constexpr ModInt& operator *= (const ModInt& a) { return *this = *this * a; }
    constexpr ModInt& operator /= (const ModInt& a) { return *this = *this / a; }

    friend constexpr ModInt operator + (ll a, const ModInt& b) {
        return ModInt()._set(a % MD + b.x);
    }
    friend constexpr ModInt operator - (ll a, const ModInt& b) {
        return ModInt()._set(a % MD - b.x + MD);
    }
    friend constexpr ModInt operator * (ll a, const ModInt& b) {
        return ModInt()._set(a % MD * b.x % MD);
    }
    friend constexpr ModInt operator / (ll a, const ModInt& b) {
        return ModInt()._set(a % MD * b.inv().x % MD);
    }

    constexpr bool operator == (const ModInt& a) const { return x == a.x; }
    constexpr bool operator != (const ModInt& a) const { return x != a.x; }

    friend std::istream& operator >> (std::istream& is, ModInt& other) {
        ll val; is >> val;
        other = ModInt(val);
        return is;
    }
    constexpr friend std::ostream& operator << (std::ostream& os, const ModInt& other) {
        return os << other.x;
    }

    constexpr ModInt pow(ll k) const {
        ModInt ans = 1, tmp = x;
        while (k) {
            if (k & 1) ans *= tmp;
            tmp *= tmp;
            k >>= 1;
        }
        return ans;
    }

    constexpr ModInt inv() const {
        if (x < 1000111) {
            _precalc(1000111);
            return invs[x];
        }
        int a = x, b = MD, ax = 1, bx = 0;
        while (b) {
            int q = a/b, t = a%b;
            a = b; b = t;
            t = ax - bx*q;
            ax = bx; bx = t;
        }
        assert(a == 1);
        if (ax < 0) ax += MD;
        return ax;
    }

    static std::vector<ModInt> factorials, inv_factorials, invs;
    constexpr static void _precalc(int n) {
        if (factorials.empty()) {
            factorials = {1};
            inv_factorials = {1};
            invs = {0};
        }
        if (n > MD) n = MD;
        int old_sz = factorials.size();
        if (n <= old_sz) return;

        factorials.resize(n);
        inv_factorials.resize(n);
        invs.resize(n);

        for (int i = old_sz; i < n; ++i) factorials[i] = factorials[i-1] * i;
        inv_factorials[n-1] = factorials.back().pow(MD - 2);
        for (int i = n - 2; i >= old_sz; --i) inv_factorials[i] = inv_factorials[i+1] * (i+1);
        for (int i = n-1; i >= old_sz; --i) invs[i] = inv_factorials[i] * factorials[i-1];
    }

    static int get_primitive_root() {
        static int primitive_root = 0;
        if (!primitive_root) {
            primitive_root = [&]() {
                std::set<int> fac;
                int v = MD - 1;
                for (ll i = 2; i * i <= v; i++)
                    while (v % i == 0) fac.insert(i), v /= i;
                if (v > 1) fac.insert(v);
                for (int g = 1; g < MD; g++) {
                    bool ok = true;
                    for (auto i : fac)
                        if (ModInt(g).pow((MD - 1) / i) == 1) {
                            ok = false;
                            break;
                        }
                    if (ok) return g;
                }
                return -1;
            }();
        }
        return primitive_root;
    }

    static ModInt C(int n, int k) {
        _precalc(n + 1);
        return factorials[n] * inv_factorials[k] * inv_factorials[n-k];
    }
    
private:
    // Internal, DO NOT USE.
    // val must be in [0, 2*MD)
    constexpr inline __attribute__((always_inline)) ModInt& _set(ll v) {
        x = v >= MD ? v - MD : v;
        return *this;
    }
};
template <int MD> std::vector<ModInt<MD>> ModInt<MD>::factorials = {1};
template <int MD> std::vector<ModInt<MD>> ModInt<MD>::inv_factorials = {1};
template <int MD> std::vector<ModInt<MD>> ModInt<MD>::invs = {0};
// }}}
#line 7 "DataStructure/test/link_cut_tree_vertexsetpathcomposite.test.cpp"
using modular = ModInt<998244353>;

#define PATH_QUERIES_ONLY
struct T {
    modular a, b;

    T() : a(1), b(0) {}
    T(modular _a, modular _b) : a(_a), b(_b) {}

    // return f(g())
    T operator + (const T& g) const {
        return T {
            a * g.a,
            a * g.b + b,
        };
    }

    T operator += (const T& g) {
        b = a * g.b + b;
        a = a * g.a;
        return *this;
    }
};
#line 1 "DataStructure/LinkCutTree.h"
// copied from https://codeforces.com/blog/entry/75885
// - Index from 1
// - T needs to support + operation
//   For subtree queries -> requires - operation
//   --> see this comment for how to handle it: https://codeforces.com/blog/entry/67637?#comment-650424
// - Not using template here, since inheritance becomes very ugly
// - Doesn't support lazy update (so no subtree updates)
// - For query on *edge* weights (instead of vertex weights)
//   --> for each edge, add a new node in LinkCut tree.
//       See https://oj.vnoi.info/problem/icpc22_mn_b for example
//
// Tested:
// - https://judge.yosupo.jp/problem/dynamic_tree_subtree_add_subtree_sum
// - https://judge.yosupo.jp/problem/dynamic_tree_vertex_set_path_composite
// - https://judge.yosupo.jp/problem/dynamic_tree_vertex_add_subtree_sum
// - (edge weights) https://oj.vnoi.info/problem/icpc22_mn_b
// - (link, cut, connected) https://www.spoj.com/problems/DYNACON1/

// Add this for path queries only
// #define PATH_QUERIES_ONLY

// TODO: Specify T
// using T = long long;
// Link Cut Tree {{{
// SplayTree {{{
struct SplayTree { // can we replace SplayTreeById and use this only?
    struct Node {
        array<int, 2> child = {0, 0};
        int parent = 0;

        // Path aggregates
        // - path[0] = go from left -> right
        // - path[1] = go from right -> left
        array<T, 2> path;  // default to T constructor
        T self;

        // Subtree aggregates
        T sub, vir;

        bool reverse = false;
    };
    vector<Node> nodes;

    SplayTree(int n) : nodes(n + 1) {}

    void splay(int x) {
        for (pushDown(x); ~getDirection(x); ) {
            int y = nodes[x].parent;
            int z = nodes[y].parent;
            pushDown(z);
            pushDown(y);
            pushDown(x);
            int dx = getDirection(x);
            int dy = getDirection(y);
            if (~dy) rotate(dx != dy ? x : y);
            rotate(x);
        }
    }

// private:
    // Return t where nodes[parent(x)].child[t] == x
    int getDirection(int x) {
        int p = nodes[x].parent;
        if (!p) return -1;
        return nodes[p].child[0] == x ? 0 : nodes[p].child[1] == x ? 1 : -1;
    }

    /**
     * Before:
     *    z
     *    |
     *    y
     *   /
     *  x
     *   \
     *   xchild
     * 
     * After:
     *    z
     *    |
     *    x
     *     \
     *      y
     *     /
     *   xchild
     */
    void rotate(int x) {
        int y = nodes[x].parent, dx = getDirection(x);
        int z = nodes[y].parent, dy = getDirection(y);

        setChild(y, nodes[x].child[!dx], dx);
        setChild(x, y, !dx);
        if (~dy) setChild(z, x, dy);
        nodes[x].parent = z;
    }

    void pushDown(int x) {
        if (!x) return;
        if (nodes[x].reverse) {
            auto [l, r] = nodes[x].child;
            nodes[l].reverse ^= 1;
            nodes[r].reverse ^= 1;

            swap(nodes[x].child[0], nodes[x].child[1]);
            swap(nodes[x].path[0], nodes[x].path[1]);
            nodes[x].reverse = false;
        }
    }

    void pushUp(int x) {
        auto [l, r] = nodes[x].child;
        pushDown(l); pushDown(r);

        nodes[x].path[0] = nodes[l].path[0] + nodes[x].self + nodes[r].path[0];
        nodes[x].path[1] = nodes[r].path[1] + nodes[x].self + nodes[l].path[1];

        nodes[x].sub = nodes[x].vir + nodes[l].sub + nodes[r].sub + nodes[x].self;
    }

    void setChild(int x, int y, int dir) {
        nodes[x].child[dir] = y;
        nodes[y].parent = x;
        pushUp(x);
    }
};
// }}}

struct LinkCut : SplayTree {
    LinkCut(int n) : SplayTree(n) {}

    bool is_connected(int u, int v) {
        return LCA(u, v) > 0;
    }

    void link(int u, int v) {
        reroot(u);
        access(v);

        nodes[v].vir = nodes[v].vir + nodes[u].sub;
        nodes[u].parent = v;
        pushUp(v);
    }

    void cut(int u, int v) {
        reroot(u);
        access(v);

        nodes[v].child[0] = nodes[u].parent = 0;
        pushUp(v);
    }

    // Returns 0 if u and v are not connected
    int LCA(int u, int v) {
        if (u == v) return u;
        access(u);
        int ret = access(v);
        return nodes[u].parent ? ret : 0;
    }

    T getPath(int u, int v) {
        reroot(u);
        access(v);
        return nodes[v].path[1];
    }

    void set(int u, T val) {
        access(u);
        nodes[u].self = val;
        pushUp(u);
    }

    T get(int u) {
        return nodes[u].self;
    }

    // Get aggregate of subtree(u). v is parent of u. There must exist edge(v, u) (?)
    T getSubtree(int u, int v) {
        reroot(v); access(u);
        return nodes[u].vir + nodes[u].self;
    }

// private:
    void reroot(int x) {
        access(x);
        nodes[x].reverse ^= 1;
        pushDown(x);
    }

    int access(int x) {
        int u = x, v = 0;
        for (; u; v = u, u = nodes[u].parent) {
            splay(u);
            int& ov = nodes[u].child[1];
            nodes[u].vir = nodes[u].vir + nodes[ov].sub;
#ifndef PATH_QUERIES_ONLY
            // T requires subtract for subtree queries
            nodes[u].vir -= nodes[v].sub;
#endif

            ov = v; pushUp(u);
        }
        return splay(x), v;
    }
};
// }}}

// Example for custom type: // https://judge.yosupo.jp/problem/dynamic_tree_vertex_set_path_composite {{{
// Since T doesn't support subtract -> comment out line
//   nodes[u].vir -= nodes[v].sub
/**
struct T {
    modular a, b;

    T() : a(1), b(0) {}
    T(modular _a, modular _b) : a(_a), b(_b) {}

    // return f(g())
    T operator + (const T& g) const {
        return T {
            a * g.a,
            a * g.b + b,
        };
    }

    T operator += (const T& g) {
        b = a * g.b + b;
        a = a * g.a;
        return *this;
    }
};
*/
// }}}
#line 31 "DataStructure/test/link_cut_tree_vertexsetpathcomposite.test.cpp"

#define FOR(i, a, b) for (int i = (a), _##i = (b); i <= _##i; ++i)
#define REP(i, a) for (int i = 0, _##i = (a); i < _##i; ++i)

int32_t main() {
    ios::sync_with_stdio(0); cin.tie(0);

    int n, q; cin >> n >> q;
    LinkCut tree(n);

    FOR(i,1,n) {
        modular a, b; cin >> a >> b;
        tree.set(i, T{a, b});
    }

    REP(i,n-1) {
        int u, v; cin >> u >> v;
        ++u; ++v;
        tree.link(u, v);
    }

    while (q--) {
        int typ; cin >> typ;
        if (typ == 0) {  // remove (u, v), add (w, x)
            int u, v, w, x; cin >> u >> v >> w >> x;
            ++u; ++v;
            ++w; ++x;
            tree.cut(u, v);
            tree.link(w, x);
        } else if (typ == 1) {  // set f(p) = cx + d
            int p; cin >> p;
            ++p;
            modular c, d; cin >> c >> d;
            tree.set(p, T{c, d});
        } else if (typ == 2) {  // get path (u, v) and apply f(x)
            int u, v; cin >> u >> v;
            ++u; ++v;
            modular x; cin >> x;

            auto f = tree.getPath(u, v);
            cout << f.a * x + f.b << '\n';
        }
    }
    return 0;
}
Back to top page