test/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/vertex_set_path_composite

Depends on

• Segment Tree (data_structure/segment_tree.hpp)
• data_structure/tree/heavy_light_decomposition.hpp

Code

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

#include <algorithm>  // for reverse
#include <data_structure/segment_tree.hpp>
#include <data_structure/tree/heavy_light_decomposition.hpp>  // for HeavyLightDecomposition
#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 <format>                                             // for vector
#include <iterator>                                           // for pair
#include <templates/macro/abbrev/eb.hpp>                      // for eb
#include <templates/macro/abbrev/endl.hpp>                    // for endl
#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 <type_traits>  // for __decay_and_strip
#include <utility>      // for pair, make_pair
#include <vector>       // for vector

using namespace std;

int main() {
    int n, q;
    cin >> n >> q;
    vector<pair<ull, ull>> a(n);
    cin >> a;
    vector<vector<int>> g(n);
    rep(i, n - 1) {
        int u, v;
        cin >> u >> v;
        g[u].eb(v);
        g[v].eb(u);
    }
    HeavyLightDecomposition<SegmentTree<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);
                                        },
                                        []() { return MP(1, 0); }>>
        hld(g, a);
    rep(_, q) {
        int T, u, v, x;
        cin >> T >> u >> v >> x;
        if (T == 0) {
            hld.set(u, {v, x});
        } else {
            auto it = hld(u, v);
            ull ans = (it.first * x) + it.second;
            ans %= MOD1;
            cout << ans << endl;
        }
    }
}

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

#include <algorithm>  // for reverse
#include <data_structure/segment_tree.hpp>
#include <data_structure/tree/heavy_light_decomposition.hpp>  // for HeavyLightDecomposition
#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 <format>                                             // for vector
#include <iterator>                                           // for pair
#include <templates/macro/abbrev/eb.hpp>                      // for eb
#include <templates/macro/abbrev/endl.hpp>                    // for endl
#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 <type_traits>  // for __decay_and_strip
#include <utility>      // for pair, make_pair
#include <vector>       // for vector

using namespace std;

int main() {
    int n, q;
    cin >> n >> q;
    vector<pair<ull, ull>> a(n);
    cin >> a;
    vector<vector<int>> g(n);
    rep(i, n - 1) {
        int u, v;
        cin >> u >> v;
        g[u].eb(v);
        g[v].eb(u);
    }
    HeavyLightDecomposition<SegmentTree<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);
                                        },
                                        []() { return MP(1, 0); }>>
        hld(g, a);
    rep(_, q) {
        int T, u, v, x;
        cin >> T >> u >> v >> x;
        if (T == 0) {
            hld.set(u, {v, x});
        } else {
            auto it = hld(u, v);
            ull ans = (it.first * x) + it.second;
            ans %= MOD1;
            cout << ans << endl;
        }
    }
}

Test cases

Env	Name	Status	Elapsed	Memory
g++	almost_line_00	AC	314 ms	80 MB
g++	almost_line_01	AC	242 ms	81 MB
g++	example_00	AC	5 ms	4 MB
g++	example_01	AC	4 ms	4 MB
g++	line_00	AC	226 ms	80 MB
g++	line_01	AC	240 ms	80 MB
g++	long-path-decomposition_killer_00	AC	131 ms	78 MB
g++	max_random_00	AC	286 ms	79 MB
g++	max_random_01	AC	280 ms	79 MB
g++	max_random_02	AC	279 ms	79 MB
g++	random_00	AC	170 ms	48 MB
g++	random_01	AC	203 ms	69 MB
g++	random_02	AC	102 ms	26 MB
g++	small_00	AC	6 ms	4 MB
g++	small_01	AC	5 ms	4 MB
g++	small_02	AC	5 ms	4 MB
g++	small_03	AC	6 ms	4 MB
g++	small_04	AC	5 ms	4 MB
g++	worst_for_path_decomposition_00	AC	494 ms	79 MB
g++	worst_for_path_decomposition_01	AC	499 ms	79 MB

Back to top page