library
This documentation is automatically generated by online-judge-tools/verification-helper
test/verify/yosupo-vertex-add-subtree-sum.test.cpp
- View this file on GitHub
- Last update: 2025-03-23 01:11:28+09:00
- Problem: https://judge.yosupo.jp/problem/vertex_add_subtree_sum
- Link: https://en.wikipedia.org/wiki/Fenwick_tree
Depends on
- graph/graph_template.hpp
- Heavy-Light Decomposition(HL分解, HLD)
(graph/tree/heavy_light_decomposition.hpp)
- template/template.hpp
Code
#define PROBLEM "https://judge.yosupo.jp/problem/vertex_add_subtree_sum"
#include "template/template.hpp"
#include <vector>
#include <type_traits>
namespace atcoder {
namespace internal {
#ifndef _MSC_VER
template <class T>
using is_signed_int128 =
typename std::conditional<std::is_same<T, __int128_t>::value ||
std::is_same<T, __int128>::value,
std::true_type,
std::false_type>::type;
template <class T>
using is_unsigned_int128 =
typename std::conditional<std::is_same<T, __uint128_t>::value ||
std::is_same<T, unsigned __int128>::value,
std::true_type,
std::false_type>::type;
template <class T>
using make_unsigned_int128 =
typename std::conditional<std::is_same<T, __int128_t>::value,
__uint128_t,
unsigned __int128>;
template <class T>
using is_integral = typename std::conditional<std::is_integral<T>::value ||
is_signed_int128<T>::value ||
is_unsigned_int128<T>::value,
std::true_type,
std::false_type>::type;
template <class T>
using is_signed_int = typename std::conditional<(is_integral<T>::value &&
std::is_signed<T>::value) ||
is_signed_int128<T>::value,
std::true_type,
std::false_type>::type;
template <class T>
using is_unsigned_int =
typename std::conditional<(is_integral<T>::value &&
std::is_unsigned<T>::value) ||
is_unsigned_int128<T>::value,
std::true_type,
std::false_type>::type;
template <class T>
using to_unsigned = typename std::conditional<
is_signed_int128<T>::value,
make_unsigned_int128<T>,
typename std::conditional<std::is_signed<T>::value,
std::make_unsigned<T>,
std::common_type<T>>::type>::type;
#else
template <class T> using is_integral = typename std::is_integral<T>;
template <class T>
using is_signed_int =
typename std::conditional<is_integral<T>::value && std::is_signed<T>::value,
std::true_type,
std::false_type>::type;
template <class T>
using is_unsigned_int =
typename std::conditional<is_integral<T>::value &&
std::is_unsigned<T>::value,
std::true_type,
std::false_type>::type;
template <class T>
using to_unsigned = typename std::conditional<is_signed_int<T>::value,
std::make_unsigned<T>,
std::common_type<T>>::type;
#endif
template <class T>
using is_signed_int_t = std::enable_if_t<is_signed_int<T>::value>;
template <class T>
using is_unsigned_int_t = std::enable_if_t<is_unsigned_int<T>::value>;
template <class T> using to_unsigned_t = typename to_unsigned<T>::type;
} // namespace internal
} // namespace atcoder
namespace atcoder {
// Reference: https://en.wikipedia.org/wiki/Fenwick_tree
template <class T> struct fenwick_tree {
using U = internal::to_unsigned_t<T>;
public:
fenwick_tree() : _n(0) {}
explicit fenwick_tree(int n) : _n(n), data(n) {}
void add(int p, T x) {
assert(0 <= p && p < _n);
p++;
while (p <= _n) {
data[p - 1] += U(x);
p += p & -p;
}
}
T sum(int l, int r) {
assert(0 <= l && l <= r && r <= _n);
return sum(r) - sum(l);
}
private:
int _n;
std::vector<U> data;
U sum(int r) {
U s = 0;
while (r > 0) {
s += data[r - 1];
r -= r & -r;
}
return s;
}
};
} // namespace atcoder
#include "graph/tree/heavy_light_decomposition.hpp"
int main() {
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int N, Q; cin >> N >> Q;
vector<int>a(N);
for(int i=0; i<N; i++) cin >> a[i];
HaruiLib::HLD hld(N);
for (int i=1; i<N; i++) {
int p; cin >> p;
hld.graph.add_edge(i,p);
hld.graph.add_edge(p,i);
}
hld.build();
atcoder::fenwick_tree<ll> fw(N);
for (int i=0; i<N; i++) {
fw.add(hld.id[i], a[i]);
}
for (int q=0; q<Q; q++) {
int op; cin >> op;
if (op == 0) {
int u, x; cin >> u >> x;
fw.add(hld.id[u], x);
}
else if (op == 1) {
int u; cin >> u;
auto [l,r] = hld.subtree_query(u);
cout << fw.sum(l, r) << endl;;
}
}
return 0;
}#line 1 "test/verify/yosupo-vertex-add-subtree-sum.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/vertex_add_subtree_sum"
#line 1 "template/template.hpp"
#include <iostream>
#include <cassert>
using namespace std;
using ll = long long;
template<class T> inline bool chmax(T& a, const T& b) {if (a<b) {a=b; return true;} return false;}
template<class T> inline bool chmin(T& a, const T& b) {if (b<a) {a=b; return true;} return false;}
const int INTINF = 1000001000;
const int INTMAX = 2147483647;
const ll LLMAX = 9223372036854775807;
const ll LLINF = 1000000000000000000;
#line 3 "test/verify/yosupo-vertex-add-subtree-sum.test.cpp"
#include <vector>
#include <type_traits>
namespace atcoder {
namespace internal {
#ifndef _MSC_VER
template <class T>
using is_signed_int128 =
typename std::conditional<std::is_same<T, __int128_t>::value ||
std::is_same<T, __int128>::value,
std::true_type,
std::false_type>::type;
template <class T>
using is_unsigned_int128 =
typename std::conditional<std::is_same<T, __uint128_t>::value ||
std::is_same<T, unsigned __int128>::value,
std::true_type,
std::false_type>::type;
template <class T>
using make_unsigned_int128 =
typename std::conditional<std::is_same<T, __int128_t>::value,
__uint128_t,
unsigned __int128>;
template <class T>
using is_integral = typename std::conditional<std::is_integral<T>::value ||
is_signed_int128<T>::value ||
is_unsigned_int128<T>::value,
std::true_type,
std::false_type>::type;
template <class T>
using is_signed_int = typename std::conditional<(is_integral<T>::value &&
std::is_signed<T>::value) ||
is_signed_int128<T>::value,
std::true_type,
std::false_type>::type;
template <class T>
using is_unsigned_int =
typename std::conditional<(is_integral<T>::value &&
std::is_unsigned<T>::value) ||
is_unsigned_int128<T>::value,
std::true_type,
std::false_type>::type;
template <class T>
using to_unsigned = typename std::conditional<
is_signed_int128<T>::value,
make_unsigned_int128<T>,
typename std::conditional<std::is_signed<T>::value,
std::make_unsigned<T>,
std::common_type<T>>::type>::type;
#else
template <class T> using is_integral = typename std::is_integral<T>;
template <class T>
using is_signed_int =
typename std::conditional<is_integral<T>::value && std::is_signed<T>::value,
std::true_type,
std::false_type>::type;
template <class T>
using is_unsigned_int =
typename std::conditional<is_integral<T>::value &&
std::is_unsigned<T>::value,
std::true_type,
std::false_type>::type;
template <class T>
using to_unsigned = typename std::conditional<is_signed_int<T>::value,
std::make_unsigned<T>,
std::common_type<T>>::type;
#endif
template <class T>
using is_signed_int_t = std::enable_if_t<is_signed_int<T>::value>;
template <class T>
using is_unsigned_int_t = std::enable_if_t<is_unsigned_int<T>::value>;
template <class T> using to_unsigned_t = typename to_unsigned<T>::type;
} // namespace internal
} // namespace atcoder
namespace atcoder {
// Reference: https://en.wikipedia.org/wiki/Fenwick_tree
template <class T> struct fenwick_tree {
using U = internal::to_unsigned_t<T>;
public:
fenwick_tree() : _n(0) {}
explicit fenwick_tree(int n) : _n(n), data(n) {}
void add(int p, T x) {
assert(0 <= p && p < _n);
p++;
while (p <= _n) {
data[p - 1] += U(x);
p += p & -p;
}
}
T sum(int l, int r) {
assert(0 <= l && l <= r && r <= _n);
return sum(r) - sum(l);
}
private:
int _n;
std::vector<U> data;
U sum(int r) {
U s = 0;
while (r > 0) {
s += data[r - 1];
r -= r & -r;
}
return s;
}
};
} // namespace atcoder
#line 1 "graph/tree/heavy_light_decomposition.hpp"
#line 5 "graph/tree/heavy_light_decomposition.hpp"
#include <algorithm>
#line 7 "graph/tree/heavy_light_decomposition.hpp"
#include <utility>
#line 1 "graph/graph_template.hpp"
#line 5 "graph/graph_template.hpp"
template <typename T>
struct Edge {
int from; int to;
T cost;
// default constructor
Edge () : from(-1), to(-1), cost(T(0)) {}
Edge(int _from, int _to, T _cost) : from(_from), to(_to), cost(_cost) {}
// unweighted
Edge(int _from, int _to) : from(_from), to(_to), cost(T(1)) {}
bool operator==(const Edge& rhs) const {
return from == rhs.from && to == rhs.to && cost == rhs.cost;
}
bool operator<(const Edge& rhs) const {
return cost < rhs.cost;
}
bool operator>(const Edge& rhs) const {
return cost > rhs.cost;
}
};
template <typename T>
struct Graph : std::vector<std::vector<Edge<T>>> {
using std::vector<std::vector<Edge<T>>>::vector; // inherit constructors
void add_edge(int i, Edge<T> e) {
(*this)[i].push_back(e);
}
void add_edge(Edge<T> e) {
(*this)[e.from].push_back(e);
}
// weighted
void add_edge(int _from, int _to, T _cost) {
(*this)[_from].push_back(Edge(_from, _to, _cost));
}
// unweighted
void add_edge(int _from, int _to) {
(*this)[_from].push_back(Edge(_from, _to, T(1)));
}
};
#line 10 "graph/tree/heavy_light_decomposition.hpp"
namespace HaruiLib {
// cf : https://ngtkana.hatenablog.com/entry/2024/06/24/200138
struct Interval {
// top_id : interval のもっとも根に近い頂点のid
// bottom_id : interval のもっとも葉に近い頂点のid
// last : LCAを含む interval であるかどうか
// reverse : from → to と top → bottomが逆向きかどうか
int top_id, bottom_id;
bool last;
bool reverse;
Interval(int _top_id, int _bottom_id, bool _last, bool _reverse) : top_id(_top_id), bottom_id(_bottom_id), last(_last), reverse(_reverse) {
}
};
using Path = std::vector<Interval>;
/*
木をいくつかのパスに分けるアルゴリズム。
うまくDFSしてパスに分けると、同じパスの中でidが連続するので、一つのパスの中ではセグメント木などの列に対してのアルゴリズムが使えるようになる。
頂点属性の問題はかんたん。
辺属性の問題は、辺の子側の頂点にその情報をもたせて管理するといい。 そのときはLCAに注意する。
*/
struct HLD {
private:
bool is_built = false;
public:
//vector<vector<int>>children;
std::vector<int> parent;
std::vector<int> id; // id[v] := 頂点vがdfs順で何番目にあるか。 HLDで分割したパスの中では、深さが浅い方から深い方へidが連続して増えていく。
std::vector<int> id2;
std::vector<int> head; // head[v] := 頂点vが所属する分割されたパスの、一番根に近い頂点。
std::vector<int> depth; // depth[v] := 頂点vの深さ
Graph<int> graph;
HLD (int N) : parent(std::vector<int>(N, -1)), id(std::vector<int>(N)), id2(std::vector<int>(N)), head(std::vector<int>(N)), depth(std::vector<int>(N)), graph(N) {}
void build(int root=0) {
dfs_sz(root);
int k = 0; dfs_hld(root, k);
is_built = true;
}
int dfs_sz(int v) {
int ret = 1, mx_sz = 0;
for (Edge<int>& nxt : graph[v]) {
if (nxt.to == parent[v]) continue;
parent[nxt.to] = v;
depth[nxt.to] = depth[v] + 1;
int sz = dfs_sz(nxt.to);
ret += sz;
if (mx_sz < sz) {
mx_sz = sz;
std::swap(graph[v][0], nxt);
}
}
return ret;
}
void dfs_hld(int v, int& k) {
id[v] = k; k++;
for (Edge e : graph[v]) {
if (e.to == parent[v]) continue;
// 今見ている辺が最大連結成分方向への辺なら,head[e.to] = head[v]
// そうでないなら、head[e.to] = e.to;
head[e.to] = (e == graph[v][0] ? head[v] : e.to);
dfs_hld(e.to, k);
}
id2[v] = k;
}
int lca(int u, int v) {
assert(is_built);
while (true) {
if (id[u] > id[v]) std::swap(u, v);
if (head[u] == head[v]) return u;
v = parent[head[v]];
}
}
Path get_path(int u, int v) {
assert(is_built);
Path upath, vpath;
while (head[u] != head[v]) {
// ちなみにu,vのdepthの大小関係は変わり続けることもある。
// 10 → 12など。
// v's head is deeper
if (depth[head[v]] >= depth[head[u]]) {
assert(depth[head[v]] >= depth[head[u]]);
/*
/ : heavy edge
.... : light edge
head[u]
/
/...
u ...
/ head[v]
/ \
/ \
/ v
*/
// u→v なのでreverse=false
vpath.emplace_back(id[head[v]], id[v], false, false);
v = parent[head[v]];
}
// u's head is deeper
else if (depth[head[v]] < depth[head[u]]) {
/*
/ : heavy edge
.... : light edge
head[v]
/
/...
v ...
/ head[u]
/ \
/ \
/ u
*/
//
upath.emplace_back(id[head[u]], id[u], false, true);
u = parent[head[u]];
}
}
// v is deeper
/*
u
/
/ ←↓
/
v
*/
if (depth[v] > depth[u]) {
upath.emplace_back(id[u], id[v], true, false);
}
// u is deeper
/*
v
/
/ →↑
/
u
*/
else {
upath.emplace_back(id[v], id[u], true, true);
}
Path retpath = upath;
std::reverse(vpath.begin(), vpath.end());
for (Interval path : vpath) retpath.push_back(path);
return retpath;
}
std::pair<int,int> subtree_query(int r) {
assert(r < int(id.size()));
return std::make_pair(id[r], id2[r]);
}
};
}
#line 139 "test/verify/yosupo-vertex-add-subtree-sum.test.cpp"
int main() {
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int N, Q; cin >> N >> Q;
vector<int>a(N);
for(int i=0; i<N; i++) cin >> a[i];
HaruiLib::HLD hld(N);
for (int i=1; i<N; i++) {
int p; cin >> p;
hld.graph.add_edge(i,p);
hld.graph.add_edge(p,i);
}
hld.build();
atcoder::fenwick_tree<ll> fw(N);
for (int i=0; i<N; i++) {
fw.add(hld.id[i], a[i]);
}
for (int q=0; q<Q; q++) {
int op; cin >> op;
if (op == 0) {
int u, x; cin >> u >> x;
fw.add(hld.id[u], x);
}
else if (op == 1) {
int u; cin >> u;
auto [l,r] = hld.subtree_query(u);
cout << fw.sum(l, r) << endl;;
}
}
return 0;
}