test/yosupo/dynamic_tree_vertex_set_path_composite.test.cpp

View this file on GitHub
Last update: 2024-05-07 01:20:48+09:00
Problem: https://judge.yosupo.jp/problem/dynamic_tree_vertex_set_path_composite

Depends on

Code

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

#include <bits/stdc++.h>

#include "../../math/modint.hpp"
#include "../../tree/link_cut_tree.hpp"
using namespace std;

using mint = Modint<998244353>;

struct AffineMonoid {
    using T = pair<pair<mint, mint>, pair<mint, mint>>;
    static T id() { return {{1, 0}, {1, 0}}; }
    static T op(T a, T b) {
        return {
            {a.first.first * b.first.first,
             a.first.second * b.first.first + b.first.second},
            {b.second.first * a.second.first,
             b.second.second * a.second.first + a.second.second},
        };
    }
};

AffineMonoid::T flip(AffineMonoid::T a) {
    swap(a.first, a.second);
    return a;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, Q;
    cin >> N >> Q;
    LinkCutTree<AffineMonoid, flip> lct(N);
    for (int i = 0; i < N; ++i) {
        int a, b;
        cin >> a >> b;
        lct.set(i, {{a, b}, {a, b}});
    }
    for (int i = 0; i < N - 1; ++i) {
        int u, v;
        cin >> u >> v;
        lct.link(u, v);
    }
    for (int i = 0; i < Q; ++i) {
        int t;
        cin >> t;
        if (t == 0) {
            int u, v, w, x;
            cin >> u >> v >> w >> x;
            lct.evert(u);
            lct.cut(v);
            lct.link(w, x);
        } else if (t == 1) {
            int p, c, d;
            cin >> p >> c >> d;
            lct.set(p, {{c, d}, {c, d}});
        } else {
            int u, v, x;
            cin >> u >> v >> x;
            auto f = lct.fold(u, v);
            cout << f.first.first * x + f.first.second << "\n";
        }
    }
}

#line 1 "test/yosupo/dynamic_tree_vertex_set_path_composite.test.cpp"
#define PROBLEM \
    "https://judge.yosupo.jp/problem/dynamic_tree_vertex_set_path_composite"

#include <bits/stdc++.h>

#line 4 "math/modint.hpp"

/**
 * @brief Mod int
 */
template <int m>
class Modint {
    using mint = Modint;
    static_assert(m > 0, "Modulus must be positive");

   public:
    static constexpr int mod() { return m; }

    constexpr Modint(long long y = 0) : x(y >= 0 ? y % m : (y % m + m) % m) {}

    constexpr int val() const { return x; }

    constexpr mint& operator+=(const mint& r) {
        if ((x += r.x) >= m) x -= m;
        return *this;
    }
    constexpr mint& operator-=(const mint& r) {
        if ((x += m - r.x) >= m) x -= m;
        return *this;
    }
    constexpr mint& operator*=(const mint& r) {
        x = static_cast<int>(1LL * x * r.x % m);
        return *this;
    }
    constexpr mint& operator/=(const mint& r) { return *this *= r.inv(); }

    constexpr bool operator==(const mint& r) const { return x == r.x; }

    constexpr mint operator+() const { return *this; }
    constexpr mint operator-() const { return mint(-x); }

    constexpr friend mint operator+(const mint& l, const mint& r) {
        return mint(l) += r;
    }
    constexpr friend mint operator-(const mint& l, const mint& r) {
        return mint(l) -= r;
    }
    constexpr friend mint operator*(const mint& l, const mint& r) {
        return mint(l) *= r;
    }
    constexpr friend mint operator/(const mint& l, const mint& r) {
        return mint(l) /= r;
    }

    constexpr mint inv() const {
        int a = x, b = m, u = 1, v = 0;
        while (b > 0) {
            int t = a / b;
            std::swap(a -= t * b, b);
            std::swap(u -= t * v, v);
        }
        return mint(u);
    }

    constexpr mint pow(long long n) const {
        mint ret(1), mul(x);
        while (n > 0) {
            if (n & 1) ret *= mul;
            mul *= mul;
            n >>= 1;
        }
        return ret;
    }

    friend std::ostream& operator<<(std::ostream& os, const mint& r) {
        return os << r.x;
    }

    friend std::istream& operator>>(std::istream& is, mint& r) {
        long long t;
        is >> t;
        r = mint(t);
        return is;
    }

   private:
    int x;
};
#line 5 "tree/link_cut_tree.hpp"

template <typename M, typename M::T (*flip)(typename M::T)>
class LinkCutTree {
    using T = M::T;

   public:
    LinkCutTree() = default;
    explicit LinkCutTree(int n) {
        for (int i = 0; i < n; ++i) {
            vertex.push_back(std::make_shared<Node>(M::id()));
        }
    }

    void link(int v, int p) {
        evert(v);
        expose(vertex[p]);
        vertex[v]->par = vertex[p];
        vertex[p]->right = vertex[v];
        recalc(vertex[p]);
    }

    void cut(int v) {
        expose(vertex[v]);
        auto p = vertex[v]->left;
        vertex[v]->left = p->par = nullptr;
        recalc(vertex[v]);
    }

    void evert(int v) {
        expose(vertex[v]);
        reverse(vertex[v]);
    }

    int par(int v) { return vertex[v]->par ? vertex[v]->par->label : -1; }

    T get(int v) const { return vertex[v]->val; }

    void set(int v, const T& x) {
        expose(vertex[v]);
        vertex[v]->val = x;
        recalc(vertex[v]);
    }

    T fold(int u, int v) {
        evert(u);
        expose(vertex[v]);
        return vertex[v]->sum;
    }

   private:
    struct Node;
    using node_ptr = std::shared_ptr<Node>;

    struct Node {
        node_ptr left, right, par;
        T val, sum;
        int sz;
        bool rev;

        Node(const T& x)
            : left(nullptr),
              right(nullptr),
              par(nullptr),
              val(x),
              sum(x),
              sz(1),
              rev(false) {}
    };

    std::vector<node_ptr> vertex;

    static void expose(node_ptr v) {
        node_ptr prev = nullptr;
        for (auto cur = v; cur; cur = cur->par) {
            splay(cur);
            cur->right = prev;
            recalc(cur);
            prev = cur;
        }
        splay(v);
    }

    // splay tree

    static int size(const node_ptr& t) { return t ? t->sz : 0; }

    static void recalc(const node_ptr& t) {
        if (!t) return;
        t->sz = size(t->left) + 1 + size(t->right);
        t->sum = t->val;
        if (t->left) t->sum = M::op(t->left->sum, t->sum);
        if (t->right) t->sum = M::op(t->sum, t->right->sum);
    }

    static void push(const node_ptr& t) {
        if (t->rev) {
            if (t->left) reverse(t->left);
            if (t->right) reverse(t->right);
            t->rev = false;
        }
    }

    static void reverse(const node_ptr& t) {
        std::swap(t->left, t->right);
        t->sum = flip(t->sum);
        t->rev ^= true;
    }

    static void rotate_left(node_ptr t) {
        node_ptr s = t->right;
        t->right = s->left;
        if (s->left) s->left->par = t;
        s->par = t->par;
        if (t->par) {
            if (t->par->left == t) {
                t->par->left = s;
            }
            if (t->par->right == t) {
                t->par->right = s;
            }
        }
        s->left = t;
        t->par = s;
        recalc(t);
        recalc(s);
    }

    static void rotate_right(node_ptr t) {
        node_ptr s = t->left;
        t->left = s->right;
        if (s->right) s->right->par = t;
        s->par = t->par;
        if (t->par) {
            if (t->par->left == t) {
                t->par->left = s;
            }
            if (t->par->right == t) {
                t->par->right = s;
            }
        }
        s->right = t;
        t->par = s;
        recalc(t);
        recalc(s);
    }

    static bool is_root(const node_ptr& t) {
        return !t->par || (t->par->left != t && t->par->right != t);
    }

    static void splay(node_ptr t) {
        push(t);
        while (!is_root(t)) {
            auto p = t->par;
            if (is_root(p)) {
                push(p);
                push(t);
                if (t == p->left)
                    rotate_right(p);
                else
                    rotate_left(p);
            } else {
                auto g = p->par;
                push(g);
                push(p);
                push(t);
                if (t == p->left) {
                    if (p == g->left) {
                        rotate_right(g);
                        rotate_right(p);
                    } else {
                        rotate_right(p);
                        rotate_left(g);
                    }
                } else {
                    if (p == g->left) {
                        rotate_left(p);
                        rotate_right(g);
                    } else {
                        rotate_left(g);
                        rotate_left(p);
                    }
                }
            }
        }
    }
};
#line 8 "test/yosupo/dynamic_tree_vertex_set_path_composite.test.cpp"
using namespace std;

using mint = Modint<998244353>;

struct AffineMonoid {
    using T = pair<pair<mint, mint>, pair<mint, mint>>;
    static T id() { return {{1, 0}, {1, 0}}; }
    static T op(T a, T b) {
        return {
            {a.first.first * b.first.first,
             a.first.second * b.first.first + b.first.second},
            {b.second.first * a.second.first,
             b.second.second * a.second.first + a.second.second},
        };
    }
};

AffineMonoid::T flip(AffineMonoid::T a) {
    swap(a.first, a.second);
    return a;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, Q;
    cin >> N >> Q;
    LinkCutTree<AffineMonoid, flip> lct(N);
    for (int i = 0; i < N; ++i) {
        int a, b;
        cin >> a >> b;
        lct.set(i, {{a, b}, {a, b}});
    }
    for (int i = 0; i < N - 1; ++i) {
        int u, v;
        cin >> u >> v;
        lct.link(u, v);
    }
    for (int i = 0; i < Q; ++i) {
        int t;
        cin >> t;
        if (t == 0) {
            int u, v, w, x;
            cin >> u >> v >> w >> x;
            lct.evert(u);
            lct.cut(v);
            lct.link(w, x);
        } else if (t == 1) {
            int p, c, d;
            cin >> p >> c >> d;
            lct.set(p, {{c, d}, {c, d}});
        } else {
            int u, v, x;
            cin >> u >> v >> x;
            auto f = lct.fold(u, v);
            cout << f.first.first * x + f.first.second << "\n";
        }
    }
}