test/dynamic_tree_vertex_set_path_composite.test.cpp

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

Depends on

• Link-Cut Tree (data_structure/link_cut_tree.hpp)
• data_structure/splay_tree.hpp

Code

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

#include <data_structure/link_cut_tree.hpp>  // for LinkCutTree
#include <fastio/base.hpp>                   // for FASTIO, cin, cout
#include <fastio/char/write.hpp>             // for operator<<
#include <fastio/pair/read.hpp>              // for operator>>
#include <fastio/signed/read.hpp>            // for operator>>
#include <fastio/unsigned/read.hpp>          // for operator>>
#include <fastio/unsigned/write.hpp>         // for operator<<
#include <fastio/vector/read.hpp>            // for operator>>
#include <iterator>                          // for pair
#include <templates/macro/abbrev/endl.hpp>   // for endl
#include <templates/macro/abbrev/ll.hpp>     // for ll
#include <templates/macro/abbrev/mp.hpp>     // for MP
#include <templates/macro/abbrev/ull.hpp>    // for ull
#include <templates/macro/mod.hpp>           // for MOD1
#include <templates/rep.hpp>                 // for rep
#include <templates/template.hpp>
#include <utility>                           // for pair, make_pair
#include <vector>                            // for vector

int main() {
    int n, q;
    cin >> n >> q;
    vector<pair<ull, ull>> a(n);
    cin >> a;
    LinkCutTree<pair<ull, ull>,
                [](pair<ull, ull> a, pair<ull, ull> b) {
                    return MP(a.first * b.first % MOD1, (a.second * b.first + b.second) % MOD1);
                },
                []() -> pair<ull, ull> { return {1, 0}; }>
        t;
    rep(i, n) {
        t.add(a[i]);
    }
    rep(_, n - 1) {
        int u, v;
        cin >> u >> v;
        t.link(u, v);
    }
    rep(_, q) {
        int T;
        cin >> T;
        if (T == 0) {
            int u, v, w, x;
            cin >> u >> v >> w >> x;
            t.cut(u, v);
            t.link(w, x);
        } else if (T == 1) {
            int p;
            ll c, d;
            cin >> p >> c >> d;
            t.set(p, {c, d});
        } else {
            int u, v;
            ll x;
            cin >> u >> v >> x;
            pair<ull, ull> ans = t(u, v);
            cout << ((ans.first * x) + ans.second) % MOD1 << endl;
        }
    }
}

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

#include <data_structure/link_cut_tree.hpp>  // for LinkCutTree
#include <fastio/base.hpp>                   // for FASTIO, cin, cout
#include <fastio/char/write.hpp>             // for operator<<
#include <fastio/pair/read.hpp>              // for operator>>
#include <fastio/signed/read.hpp>            // for operator>>
#include <fastio/unsigned/read.hpp>          // for operator>>
#include <fastio/unsigned/write.hpp>         // for operator<<
#include <fastio/vector/read.hpp>            // for operator>>
#include <iterator>                          // for pair
#include <templates/macro/abbrev/endl.hpp>   // for endl
#include <templates/macro/abbrev/ll.hpp>     // for ll
#include <templates/macro/abbrev/mp.hpp>     // for MP
#include <templates/macro/abbrev/ull.hpp>    // for ull
#include <templates/macro/mod.hpp>           // for MOD1
#include <templates/rep.hpp>                 // for rep
#include <templates/template.hpp>
#include <utility>                           // for pair, make_pair
#include <vector>                            // for vector

int main() {
    int n, q;
    cin >> n >> q;
    vector<pair<ull, ull>> a(n);
    cin >> a;
    LinkCutTree<pair<ull, ull>,
                [](pair<ull, ull> a, pair<ull, ull> b) {
                    return MP(a.first * b.first % MOD1, (a.second * b.first + b.second) % MOD1);
                },
                []() -> pair<ull, ull> { return {1, 0}; }>
        t;
    rep(i, n) {
        t.add(a[i]);
    }
    rep(_, n - 1) {
        int u, v;
        cin >> u >> v;
        t.link(u, v);
    }
    rep(_, q) {
        int T;
        cin >> T;
        if (T == 0) {
            int u, v, w, x;
            cin >> u >> v >> w >> x;
            t.cut(u, v);
            t.link(w, x);
        } else if (T == 1) {
            int p;
            ll c, d;
            cin >> p >> c >> d;
            t.set(p, {c, d});
        } else {
            int u, v;
            ll x;
            cin >> u >> v >> x;
            pair<ull, ull> ans = t(u, v);
            cout << ((ans.first * x) + ans.second) % MOD1 << endl;
        }
    }
}

Test cases

Env	Name	Status	Elapsed	Memory
g++	almost_line_00	AC	836 ms	41 MB
g++	almost_line_01	AC	803 ms	41 MB
g++	example_00	AC	5 ms	4 MB
g++	example_01	AC	4 ms	4 MB
g++	max_random_00	AC	471 ms	41 MB
g++	max_random_01	AC	479 ms	41 MB
g++	max_random_02	AC	465 ms	41 MB
g++	medium_00	AC	5 ms	4 MB
g++	medium_01	AC	5 ms	4 MB
g++	medium_02	AC	5 ms	4 MB
g++	medium_03	AC	5 ms	4 MB
g++	medium_04	AC	5 ms	4 MB
g++	random_00	AC	322 ms	29 MB
g++	random_01	AC	343 ms	32 MB
g++	random_02	AC	228 ms	17 MB
g++	random_03	AC	97 ms	31 MB
g++	random_04	AC	164 ms	11 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

Back to top page