test/dynamic_tree_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/dynamic_tree_vertex_add_path_sum

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

#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/signed/read.hpp>            // for operator>>
#include <fastio/signed/write.hpp>           // for operator<<
#include <fastio/vector/read.hpp>            // for operator>>
#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

int main() {
    int n, q;
    cin >> n >> q;
    vector<int> a(n);
    cin >> a;
    LinkCutTree<RSQ(ll, 0)> t;
    rep(i, n) {
        t.add(a[i]);
    }
    rep(_, n - 1) {
        int u, v;
        cin >> u >> v;
        t.link(u, v);
    }
    rep(_, q) {
        ll T, u, v;
        cin >> T >> u >> v;
        if (T == 0) {
            ll w, x;
            cin >> w >> x;
            t.cut(u, v);
            t.link(w, x);
        } else if (T == 1) {
            t.set(u, t[u] + v);
        } else {
            ll ans = t(u, v);
            cout << ans << endl;
        }
    }
}

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

#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/signed/read.hpp>            // for operator>>
#include <fastio/signed/write.hpp>           // for operator<<
#include <fastio/vector/read.hpp>            // for operator>>
#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

int main() {
    int n, q;
    cin >> n >> q;
    vector<int> a(n);
    cin >> a;
    LinkCutTree<RSQ(ll, 0)> t;
    rep(i, n) {
        t.add(a[i]);
    }
    rep(_, n - 1) {
        int u, v;
        cin >> u >> v;
        t.link(u, v);
    }
    rep(_, q) {
        ll T, u, v;
        cin >> T >> u >> v;
        if (T == 0) {
            ll w, x;
            cin >> w >> x;
            t.cut(u, v);
            t.link(w, x);
        } else if (T == 1) {
            t.set(u, t[u] + v);
        } else {
            ll ans = t(u, v);
            cout << ans << endl;
        }
    }
}

Test cases

Env	Name	Status	Elapsed	Memory
g++	almost_line_00	AC	712 ms	33 MB
g++	almost_line_01	AC	702 ms	33 MB
g++	example_00	AC	6 ms	4 MB
g++	max_random_00	AC	401 ms	33 MB
g++	max_random_01	AC	377 ms	33 MB
g++	max_random_02	AC	378 ms	33 MB
g++	random_00	AC	260 ms	23 MB
g++	random_01	AC	272 ms	27 MB
g++	random_02	AC	165 ms	14 MB
g++	random_03	AC	87 ms	25 MB
g++	random_04	AC	117 ms	8 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

Back to top page