test/vertex_add_path_sum.test.cpp

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

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_add_path_sum"

#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/signed/read.hpp>                             // for operator>>
#include <fastio/signed/write.hpp>                            // for operator<<
#include <fastio/vector/read.hpp>                             // for operator>>
#include <format>                                             // for vector
#include <templates/macro/abbrev/eb.hpp>                      // for eb
#include <templates/macro/abbrev/endl.hpp>                    // for endl
#include <templates/macro/abbrev/ll.hpp>                      // for ll
#include <templates/macro/segtree/RSQ.hpp>                    // for RSQ
#include <templates/rep.hpp>                                  // for rep
#include <templates/template.hpp>
#include <vector>  // for vector

using namespace std;

int main() {
    int n, q;
    cin >> n >> q;
    vector<ll> 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<RSQ(ll, 0)>> hld(g, a);
    rep(_, q) {
        int T, u, v;
        cin >> T >> u >> v;
        if (T == 0) {
            hld.add(u, v);
        } else {
            cout << hld(u, v) << endl;
        }
    }
}

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

#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/signed/read.hpp>                             // for operator>>
#include <fastio/signed/write.hpp>                            // for operator<<
#include <fastio/vector/read.hpp>                             // for operator>>
#include <format>                                             // for vector
#include <templates/macro/abbrev/eb.hpp>                      // for eb
#include <templates/macro/abbrev/endl.hpp>                    // for endl
#include <templates/macro/abbrev/ll.hpp>                      // for ll
#include <templates/macro/segtree/RSQ.hpp>                    // for RSQ
#include <templates/rep.hpp>                                  // for rep
#include <templates/template.hpp>
#include <vector>  // for vector

using namespace std;

int main() {
    int n, q;
    cin >> n >> q;
    vector<ll> 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<RSQ(ll, 0)>> hld(g, a);
    rep(_, q) {
        int T, u, v;
        cin >> T >> u >> v;
        if (T == 0) {
            hld.add(u, v);
        } else {
            cout << hld(u, v) << endl;
        }
    }
}

Test cases

Env	Name	Status	Elapsed	Memory
g++	almost_line_00	AC	650 ms	132 MB
g++	almost_line_01	AC	630 ms	131 MB
g++	example_00	AC	5 ms	4 MB
g++	line_00	AC	636 ms	130 MB
g++	line_01	AC	612 ms	131 MB
g++	long-path-decomposition_killer_00	AC	248 ms	126 MB
g++	max_random_00	AC	705 ms	127 MB
g++	max_random_01	AC	735 ms	127 MB
g++	max_random_02	AC	785 ms	127 MB
g++	random_00	AC	582 ms	107 MB
g++	random_01	AC	658 ms	120 MB
g++	random_02	AC	160 ms	24 MB
g++	random_03	AC	405 ms	115 MB
g++	random_04	AC	255 ms	89 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	5 ms	4 MB
g++	small_04	AC	5 ms	4 MB

Back to top page