test/vertex_add_subtree_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_subtree_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_subtree_sum"

#include <algorithm>  // for reverse
#include <data_structure/segment_tree.hpp>
#include <data_structure/tree/heavy_light_decomposition.hpp>  // for HeavyLi...
#include <fastio/base.hpp>                                    // for FASTIO
#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

int main() {
    int n, q;
    cin >> n >> q;
    vector<ll> a(n);
    vector<int> p(n - 1);
    cin >> a >> p;
    vector<vector<int>> g(n);
    rep(i, n - 1) {
        g[p[i]].eb(i + 1);
    }
    HeavyLightDecomposition<SegmentTree<RSQ(ll, 0)>> hld(g, a);
    rep(_, q) {
        int T, u;
        cin >> T >> u;
        if (T == 0) {
            int x;
            cin >> x;
            hld.add(u, x);
        } else {
            cout << hld.subtree(u) << endl;
        }
    }
}

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

#include <algorithm>  // for reverse
#include <data_structure/segment_tree.hpp>
#include <data_structure/tree/heavy_light_decomposition.hpp>  // for HeavyLi...
#include <fastio/base.hpp>                                    // for FASTIO
#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

int main() {
    int n, q;
    cin >> n >> q;
    vector<ll> a(n);
    vector<int> p(n - 1);
    cin >> a >> p;
    vector<vector<int>> g(n);
    rep(i, n - 1) {
        g[p[i]].eb(i + 1);
    }
    HeavyLightDecomposition<SegmentTree<RSQ(ll, 0)>> hld(g, a);
    rep(_, q) {
        int T, u;
        cin >> T >> u;
        if (T == 0) {
            int x;
            cin >> x;
            hld.add(u, x);
        } else {
            cout << hld.subtree(u) << endl;
        }
    }
}

Test cases

Env	Name	Status	Elapsed	Memory
g++	example_00	AC	34 ms	4 MB
g++	line_00	AC	290 ms	131 MB
g++	line_01	AC	279 ms	131 MB
g++	max_random_00	AC	331 ms	109 MB
g++	max_random_01	AC	333 ms	109 MB
g++	max_random_02	AC	334 ms	109 MB
g++	random_00	AC	252 ms	94 MB
g++	random_01	AC	293 ms	104 MB
g++	random_02	AC	83 ms	21 MB
g++	random_03	AC	210 ms	99 MB
g++	random_04	AC	146 ms	78 MB
g++	small_00	AC	5 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