This documentation is automatically generated by online-judge-tools/verification-helper
View the Project on GitHub shibh308/library
#define PROBLEM "https://judge.yosupo.jp/problem/vertex_add_subtree_sum" #include <bits/stdc++.h> using namespace std; using i64 = long long; #include "../lib/classes/eulertour.cpp" #include "../lib/classes/segtree.cpp" signed main(){ int n, q; cin >> n >> q; vector<i64> a(n); for(int i = 0; i < n; ++i) cin >> a[i]; vector<vector<int>> edges(n); for(int i = 1; i < n; ++i){ int p; cin >> p; edges[p].push_back(i); edges[i].push_back(p); } EulerTour et(edges); vector<i64> b(n); for(int i = 0; i < n; ++i) b[et.get_pos(i)] = a[i]; Segtree<i64> seg(n, b, [](auto x, auto y){return x + y;}, 0LL); for(int i = 0; i < q; ++i){ int type; cin >> type; if(type == 0){ int u, x; cin >> u >> x; seg.update(et.get_pos(u), x); } else{ int u; cin >> u; auto p = et.get_subtree(u); cout << seg.get(p.first, p.second) << endl; } } }
#line 1 "verify/eulertour.test.cpp" #define PROBLEM "https://judge.yosupo.jp/problem/vertex_add_subtree_sum" #include <bits/stdc++.h> using namespace std; using i64 = long long; #line 1 "lib/classes/eulertour.cpp" struct EulerTour{ int n; vector<int> in, out; EulerTour(vector<vector<int>>& edges, int par = 0) : n(edges.size()), in(n, -1), out(n, -1){ int cnt = 0; function<void(int)> f = [&](int x){ in[x] = cnt++; for(auto y : edges[x]){ if(in[y] == -1) f(y); } out[x] = cnt; }; f(par); } int get_pos(int x){ return in[x]; } // 自身を含みたくない場合は(in[x] + 1, out[x]) pair<int,int> get_subtree(int x){ return make_pair(in[x], out[x]); } }; #line 1 "lib/classes/segtree.cpp" template<typename T> struct Segtree{ int n; T op; vector<T> elm; function<T(T, T)> f; Segtree(int n, T init, function<T(T, T)> f, T op = T()) : n(n), op(op), elm(2 * n, init), f(f) { for(int i = n - 1; i >= 1; --i) elm[i] = f(elm[2 * i], elm[2 * i + 1]); } Segtree(int n, vector<T> init, function<T(T, T)> f, T op = T()) : n(n), op(op), elm(2 * n), f(f) { for(int i = 0; i < n; ++i) elm[i + n] = init[i]; for(int i = n - 1; i >= 1; --i) elm[i] = f(elm[2 * i], elm[2 * i + 1]); } void set(int x, T val){ x += n; elm[x] = val; while(x >>= 1) elm[x] = f(elm[2 * x], elm[2 * x + 1]); } void update(int x, T val){ x += n; elm[x] = f(elm[x], val); while(x >>= 1) elm[x] = f(elm[2 * x], elm[2 * x + 1]); } T get(int x, int y) const{ T l = op, r = op; for(x += n, y += n - 1; x <= y; x >>= 1, y >>= 1){ if(x & 1) l = f(l, elm[x++]); if(!(y & 1)) r = f(elm[y--], r); } return f(l, r); } }; #line 10 "verify/eulertour.test.cpp" signed main(){ int n, q; cin >> n >> q; vector<i64> a(n); for(int i = 0; i < n; ++i) cin >> a[i]; vector<vector<int>> edges(n); for(int i = 1; i < n; ++i){ int p; cin >> p; edges[p].push_back(i); edges[i].push_back(p); } EulerTour et(edges); vector<i64> b(n); for(int i = 0; i < n; ++i) b[et.get_pos(i)] = a[i]; Segtree<i64> seg(n, b, [](auto x, auto y){return x + y;}, 0LL); for(int i = 0; i < q; ++i){ int type; cin >> type; if(type == 0){ int u, x; cin >> u >> x; seg.update(et.get_pos(u), x); } else{ int u; cin >> u; auto p = et.get_subtree(u); cout << seg.get(p.first, p.second) << endl; } } }