test/yosupo/tree/dynamic_tree_vertex_set_path_composite.test.cpp

• View this file on GitHub
• Last update: 2025-10-28 09:15:43+07:00
• Problem: https://judge.yosupo.jp/problem/dynamic_tree_vertex_set_path_composite

Depends on

• Modint (math/modint.hpp)
• other/types.hpp
• Link Cut Tree (tree/link_cut.hpp)

Code

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

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

#include "tree/link_cut.hpp"
#include "math/modint.hpp"
#include "other/types.hpp"

using mint = modint998;

struct node : lct_node<node> {
    using lct_node<node>::lct_node;

    using T = array<mint, 2>;
    T val{1, 0};
    array<T, 2> path{
        {{1, 0}, {1, 0}}
    };

    void set(i32 a, i32 b) { val = {a, b}; }

    T op(T l, T r) { return {l[0] * r[0], l[0] * r[1] + l[1]}; }
    void pull() {
        path[0] = op(op($(r)->path[0], val), $(l)->path[0]);
        path[1] = op(op($(l)->path[1], val), $(r)->path[1]);
    }
    void flip() { swap(path[0], path[1]); }
};

int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    i32 n, q;
    cin >> n >> q;
    LCT<node> tr(n);
    for (i32 i = 0, a, b; i < n; i++) cin >> a >> b, tr[i]->set(a, b);
    for (i32 i = 0, u, v; i < n - 1; i++) cin >> u >> v, tr.link(u, v);
    while (q--) {
        i32 t;
        cin >> t;
        if (t == 0) {
            i32 a, b, c, d;
            cin >> a >> b >> c >> d;
            tr.cut(a, b), tr.link(c, d);
        } else if (t == 1) {
            i32 p, c, d;
            cin >> p >> c >> d;
            tr.set(p, c, d);
        } else {
            i32 u, v, x;
            cin >> u >> v >> x;
            tr.expose_path(u, v);
            auto [a, b] = tr[v]->path[0];
            cout << a * x + b << "\n";
        }
    }
}

#line 1 "test/yosupo/tree/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>
using namespace std;

#line 2 "tree/link_cut.hpp"

template<class node> struct LCT {
    using ptr = node *;
    vector<node> nodes;

    LCT(int n = 0) : nodes(n) {}

    auto operator[](int i) { return &nodes[i]; }
    int id(ptr t) { return int(t - &nodes[0]); }

    void splay(int v) { splay(&nodes[v]); }
    void expose(int v) { expose(&nodes[v]); }
    void expose_path(int u, int v) { evert(u), expose(v); }
    void evert(int v) { evert(&nodes[v]); }
    void link(int v, int p) { link(&nodes[v], &nodes[p]); }
    void cut(int v, int p) { cut(&nodes[v], &nodes[p]); }
    int lca(int u, int v) {
        ptr l = lca(&nodes[u], &nodes[v]);
        return l ? id(l) : -1;
    }
    template<class... T> void set(int v, T &&...x) {
        expose(v), nodes[v].set(x...);
    }
    template<class... T> void add(int v, T &&...x) {
        expose(v), nodes[v].add(x...);
    }

    static void splay(ptr t) {
        for (t->_push(); state(t); rot(t)) {
            ptr p = t->p, g = p->p;
            if (g) g->_push();
            p->_push(), t->_push();
            if (state(p)) rot(state(t) == state(p) ? p : t);
        }
    }
    static ptr expose(ptr t) {
        ptr prv = 0;
        for (ptr cur = t; cur; cur = cur->p) {
            splay(cur);
            if (cur->r) cur->_add_light(cur->r);
            if (prv) cur->_sub_light(prv);
            attach(cur, 1, exchange(prv, cur));
        }
        splay(t);
        return prv;
    }
    static void evert(ptr t) { expose(t), t->_flip(); }
    static void link(ptr v, ptr p) {
        evert(v), expose(p);
        assert(!v->p && !p->r);
        attach(p, 1, v);
    }
    static void cut(ptr v, ptr p) {
        evert(p), expose(v);
        assert(!v->p && v->l == p);
        attach(v, 0, p->p = 0);
    }
    static ptr lca(ptr u, ptr v) {
        if (u == v) return u;
        expose(u);
        ptr l = expose(v);
        return u->p ? l : 0;
    }

    static ptr &ch(ptr t, bool d) { return d ? t->r : t->l; }
    static void attach(ptr p, int d, ptr c) {
        if (c) c->p = p;
        ch(p, d) = c, p->pull();
    }
    static int state(ptr t) {
        if (!t->p) return 0;
        return t == t->p->l ? -1 : t == t->p->r ? 1 : 0;
    }
    static void rot(ptr t) {
        ptr p = t->p, g = p->p;
        int d = state(t) == 1, dp = state(p);
        t->p = p->p;
        if (g) dp ? attach(g, dp == 1, t) : g->_change_light(p, t);
        attach(p, d, ch(t, !d));
        attach(t, !d, p);
    }
};

template<class node> struct lct_node {
    using ptr = node *;
    static ptr $(ptr t) {
        static node nil;
        return t ?: &nil;
    }
    ptr p = 0, l = 0, r = 0;
    bool rev = 0;

    node *as_derived() { return (node *)this; };
    void _push() {
        if (exchange(rev, 0)) $(l)->_flip(), $(r)->_flip();
        if constexpr (has_push<node>) as_derived()->push();
    }
    void _flip() {
        swap(l, r), rev ^= 1;
        if constexpr (has_flip<node>) as_derived()->flip();
    }

    void _add_light(ptr c) {
        if constexpr (has_add_light<node>) as_derived()->add_light(c);
    }
    void _sub_light(ptr c) {
        if constexpr (has_sub_light<node>) as_derived()->sub_light(c);
    }
    void _change_light(ptr prv, ptr cur) {
        if constexpr (has_change_light<node>)
            as_derived()->change_light(prv, cur);
    }

// rip compile time
#define CHECK(a) \
    template<class T, class = void> struct has_##a##_t : false_type {}; \
    template<class T> struct has_##a##_t<T, void_t<decltype(&T::a)>> : true_type {}; \
    template<class T> static constexpr bool has_##a = has_##a##_t<T>::value;
    CHECK(push) CHECK(flip)
    CHECK(add_light) CHECK(sub_light) CHECK(change_light)
#undef CHECK
};
#line 2 "math/modint.hpp"

// clang-format off
template<uint32_t m> struct modint {
    static_assert(m >= 1, "Modulus must be in the range [1;2^31)");

    using mint = modint;
    static constexpr bool is_simple = true;

    static constexpr uint32_t mod() noexcept { return m; }
    constexpr modint() noexcept = default;
    constexpr modint(int64_t v) noexcept : _v(uint32_t((v %= m) < 0 ? v + m : v)) {}
    constexpr static mint raw(uint32_t v) noexcept { mint x; return x._v = v, x; }
    template<class T> constexpr explicit operator T() const noexcept { return _v; }

    constexpr mint &operator++() noexcept { return _v = ++_v == mod() ? 0 : _v, *this; }
    constexpr mint &operator--() noexcept { --(_v ? _v : _v = mod()); return *this; }
    constexpr mint operator++(int) noexcept { return exchange(*this, ++mint(*this)); }
    constexpr mint operator--(int) noexcept { return exchange(*this, --mint(*this)); }

    constexpr mint &operator+=(mint rhs) noexcept {
        return _v = int(_v += rhs._v - mod()) < 0 ? _v + mod() : _v, *this;
    }
    constexpr mint &operator-=(mint rhs) noexcept {
        return _v = int(_v -= rhs._v) < 0 ? _v + mod() : _v, *this;
    }
    constexpr mint &operator*=(mint rhs) noexcept {
        return _v = uint64_t(_v) * rhs._v % mod(), *this;
    }
    constexpr mint &operator/=(mint rhs) noexcept {
        return *this = *this * rhs.inv();
    }

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

    constexpr mint operator+() const noexcept { return *this; }
    constexpr mint operator-() const noexcept { return raw(_v ? mod() - _v : 0); }

    constexpr friend bool operator==(mint l, mint r) noexcept { return l._v == r._v; }
    constexpr friend bool operator!=(mint l, mint r) noexcept { return l._v != r._v; }
    constexpr friend bool operator<(mint l, mint r) noexcept { return l._v < r._v; }

    constexpr mint pow(uint64_t n) const noexcept {
        mint b = *this, res = 1;
        while (n) n & 1 ? res *= b : 0, b *= b, n >>= 1;
        return res;
    }

    constexpr mint inv() const noexcept {
        int a = _v, b = mod(), x = 1, y = 0;
        while (b) {
            x = exchange(y, x - a / b * y);
            a = exchange(b, a % b);
        }
        assert(a == 1);
        return x;
    }

    friend istream &operator>>(istream &is, mint &x) {
        int64_t v{};
        return is >> v, x = v, is;
    }
    friend ostream &operator<<(ostream &os, const mint &x) { return os << x._v; }

  private:
    uint32_t _v = 0;
};
using modint107 = modint<1'000'000'007>;
using modint998 = modint<998'244'353>;
// clang-format on
#line 2 "other/types.hpp"

using i8 = int8_t;
using u8 = uint8_t;
using i32 = int32_t;
using u32 = uint32_t;
using i64 = int64_t;
using u64 = uint64_t;
using f32 = float;
using f64 = double;
using f80 = long double;
using str = string;
template<class T> using vec = vector<T>;
template<class E = i32> using graph = vec<vec<E>>;
#line 9 "test/yosupo/tree/dynamic_tree_vertex_set_path_composite.test.cpp"

using mint = modint998;

struct node : lct_node<node> {
    using lct_node<node>::lct_node;

    using T = array<mint, 2>;
    T val{1, 0};
    array<T, 2> path{
        {{1, 0}, {1, 0}}
    };

    void set(i32 a, i32 b) { val = {a, b}; }

    T op(T l, T r) { return {l[0] * r[0], l[0] * r[1] + l[1]}; }
    void pull() {
        path[0] = op(op($(r)->path[0], val), $(l)->path[0]);
        path[1] = op(op($(l)->path[1], val), $(r)->path[1]);
    }
    void flip() { swap(path[0], path[1]); }
};

int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    i32 n, q;
    cin >> n >> q;
    LCT<node> tr(n);
    for (i32 i = 0, a, b; i < n; i++) cin >> a >> b, tr[i]->set(a, b);
    for (i32 i = 0, u, v; i < n - 1; i++) cin >> u >> v, tr.link(u, v);
    while (q--) {
        i32 t;
        cin >> t;
        if (t == 0) {
            i32 a, b, c, d;
            cin >> a >> b >> c >> d;
            tr.cut(a, b), tr.link(c, d);
        } else if (t == 1) {
            i32 p, c, d;
            cin >> p >> c >> d;
            tr.set(p, c, d);
        } else {
            i32 u, v, x;
            cin >> u >> v >> x;
            tr.expose_path(u, v);
            auto [a, b] = tr[v]->path[0];
            cout << a * x + b << "\n";
        }
    }
}

Test cases

Env	Name	Status	Elapsed	Memory
g++	almost_line_00	AC	601 ms	14 MB
g++	almost_line_01	AC	608 ms	14 MB
g++	example_00	AC	4 ms	4 MB
g++	example_01	AC	4 ms	4 MB
g++	issue_1216_00	AC	127 ms	14 MB
g++	max_random_00	AC	537 ms	14 MB
g++	max_random_01	AC	547 ms	14 MB
g++	max_random_02	AC	531 ms	14 MB
g++	medium_00	AC	5 ms	4 MB
g++	medium_01	AC	4 ms	4 MB
g++	medium_02	AC	4 ms	4 MB
g++	medium_03	AC	4 ms	4 MB
g++	medium_04	AC	5 ms	4 MB
g++	random_00	AC	350 ms	10 MB
g++	random_01	AC	392 ms	12 MB
g++	random_02	AC	214 ms	6 MB
g++	random_03	AC	231 ms	13 MB
g++	random_04	AC	136 ms	4 MB
g++	small_00	AC	4 ms	4 MB
g++	small_01	AC	4 ms	4 MB
g++	small_02	AC	4 ms	4 MB
g++	small_03	AC	4 ms	4 MB
g++	small_04	AC	4 ms	4 MB
clang++	almost_line_00	AC	683 ms	14 MB
clang++	almost_line_01	AC	684 ms	14 MB
clang++	example_00	AC	4 ms	4 MB
clang++	example_01	AC	4 ms	4 MB
clang++	issue_1216_00	AC	137 ms	14 MB
clang++	max_random_00	AC	634 ms	14 MB
clang++	max_random_01	AC	634 ms	14 MB
clang++	max_random_02	AC	615 ms	14 MB
clang++	medium_00	AC	5 ms	4 MB
clang++	medium_01	AC	4 ms	4 MB
clang++	medium_02	AC	4 ms	4 MB
clang++	medium_03	AC	4 ms	4 MB
clang++	medium_04	AC	5 ms	4 MB
clang++	random_00	AC	409 ms	10 MB
clang++	random_01	AC	456 ms	12 MB
clang++	random_02	AC	248 ms	6 MB
clang++	random_03	AC	271 ms	13 MB
clang++	random_04	AC	155 ms	4 MB
clang++	small_00	AC	4 ms	4 MB
clang++	small_01	AC	4 ms	4 MB
clang++	small_02	AC	4 ms	4 MB
clang++	small_03	AC	4 ms	4 MB
clang++	small_04	AC	4 ms	4 MB

Back to top page