algorithm-dev
This documentation is automatically generated by online-judge-tools/verification-helper
verify/yosupo-vertex_add_subtree_sum-heavy_light_decomposition.test.cpp
- View this file on GitHub
- Last update: 2025-07-03 00:41:25+09:00
- Problem: https://judge.yosupo.jp/problem/vertex_add_subtree_sum
- Link: View error logs on GitHub Actions
Depends on
algorithm/DataStructure/SegmentTree/binary_indexed_tree.hpp
- algorithm/Graph/Tree/heavy_light_decomposition.hpp
- algorithm/Math/Algebra/algebra.hpp
Code
#define PROBLEM "https://judge.yosupo.jp/problem/vertex_add_subtree_sum"
#include <iostream>
#include <utility>
#include <vector>
#include "../algorithm/DataStructure/SegmentTree/binary_indexed_tree.hpp"
#include "../algorithm/Graph/Tree/heavy_light_decomposition.hpp"
int main() {
int n;
int q;
std::cin >> n >> q;
std::vector<int> a(n);
for(auto &elem : a) std::cin >> elem;
algorithm::HLD hld(n);
for(int i = 1; i < n; ++i) {
int p;
std::cin >> p;
hld.add_edge(p, i);
}
hld.build();
using binary_indexed_tree = algorithm::binary_indexed_tree::range_sum_binary_indexed_tree<long long>;
using group = binary_indexed_tree::group_type;
std::vector<group> b(n);
for(int i = 0; i < n; ++i) b[hld.vertex_index()[i]] = a[i];
binary_indexed_tree bit(std::move(b));
while(q--) {
int t;
int u;
std::cin >> t >> u;
if(t == 0) {
int x;
std::cin >> x;
bit.add(hld.vertex_index(u), x);
} else {
auto &&[l, r] = hld.vertex_query_range_of_subtree(u);
auto &&ans = bit.sum(l, r);
std::cout << ans << "\n";
}
}
}#line 1 "verify/yosupo-vertex_add_subtree_sum-heavy_light_decomposition.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/vertex_add_subtree_sum"
#include <iostream>
#include <utility>
#include <vector>
#line 1 "algorithm/DataStructure/SegmentTree/binary_indexed_tree.hpp"
#include <algorithm>
#include <cassert>
#include <initializer_list>
#include <iterator>
#include <type_traits>
#line 11 "algorithm/DataStructure/SegmentTree/binary_indexed_tree.hpp"
#line 1 "algorithm/Math/Algebra/algebra.hpp"
#line 6 "algorithm/Math/Algebra/algebra.hpp"
#include <limits>
#include <numeric>
#line 10 "algorithm/Math/Algebra/algebra.hpp"
namespace algorithm {
namespace algebra {
template <typename S>
class Set {
public:
using value_type = S;
protected:
value_type val;
public:
constexpr Set() : val() {}
constexpr Set(const value_type &val) : val(val) {}
constexpr Set(value_type &&val) : val(std::move(val)) {}
friend constexpr bool operator==(const Set &lhs, const Set &rhs) { return lhs.val == rhs.val; }
friend std::istream &operator>>(std::istream &is, Set &rhs) { return is >> rhs.val; }
friend std::ostream &operator<<(std::ostream &os, const Set &rhs) { return os << rhs.val; }
constexpr value_type value() const { return val; }
};
template <typename S, auto op>
class Semigroup : public Set<S> {
static_assert(std::is_invocable_r<S, decltype(op), S, S>::value);
using base_type = Set<S>;
public:
using value_type = typename base_type::value_type;
constexpr Semigroup() : base_type() {}
constexpr Semigroup(const value_type &val) : base_type(val) {}
constexpr Semigroup(value_type &&val) : base_type(std::move(val)) {}
friend constexpr Semigroup operator*(const Semigroup &lhs, const Semigroup &rhs) { return Semigroup(op(lhs.val, rhs.val)); }
static constexpr auto get_op() { return op; }
};
template <typename S, auto op, auto e>
class Monoid : public Semigroup<S, op> {
static_assert(std::is_invocable_r<S, decltype(e)>::value);
using base_type = Semigroup<S, op>;
public:
using value_type = typename base_type::value_type;
constexpr Monoid() : base_type() {}
constexpr Monoid(const value_type &val) : base_type(val) {}
constexpr Monoid(value_type &&val) : base_type(std::move(val)) {}
friend constexpr Monoid operator*(const Monoid &lhs, const Monoid &rhs) { return Monoid(op(lhs.val, rhs.val)); }
static constexpr auto get_e() { return e; }
static constexpr Monoid one() { return Monoid(e()); } // return identity element.
};
template <typename S, auto op, auto e, auto inverse>
class Group : public Monoid<S, op, e> {
static_assert(std::is_invocable_r<S, decltype(inverse), S>::value);
using base_type = Monoid<S, op, e>;
public:
using value_type = typename base_type::value_type;
constexpr Group() : base_type() {}
constexpr Group(const value_type &val) : base_type(val) {}
constexpr Group(value_type &&val) : base_type(std::move(val)) {}
friend constexpr Group operator*(const Group &lhs, const Group &rhs) { return Group(op(lhs.val, rhs.val)); }
static constexpr auto get_inverse() { return inverse; }
static constexpr Group one() { return Group(e()); } // return identity element.
constexpr Group inv() const { return Group(inverse(this->val)); } // return inverse element.
};
template <typename F, auto compose, auto id, typename X, auto mapping>
class OperatorMonoid : public Monoid<F, compose, id> {
static_assert(std::is_invocable_r<X, decltype(mapping), F, X>::value);
using base_type = Monoid<F, compose, id>;
public:
using value_type = typename base_type::value_type;
using acted_value_type = X;
constexpr OperatorMonoid() : base_type() {}
constexpr OperatorMonoid(const value_type &val) : base_type(val) {}
constexpr OperatorMonoid(value_type &&val) : base_type(std::move(val)) {}
friend constexpr OperatorMonoid operator*(const OperatorMonoid &lhs, const OperatorMonoid &rhs) { return OperatorMonoid(compose(lhs.val, rhs.val)); }
static constexpr auto get_mapping() { return mapping; }
static constexpr OperatorMonoid one() { return OperatorMonoid(id()); } // return identity mapping.
constexpr acted_value_type act(const acted_value_type &x) const { return mapping(this->val, x); }
template <class S>
constexpr S act(const S &x) const {
static_assert(std::is_base_of<Set<acted_value_type>, S>::value);
return S(mapping(this->val, x.value()));
}
};
namespace element {
template <typename S>
constexpr auto zero = []() -> S { return S(); };
template <typename S>
constexpr auto one = []() -> S { return 1; };
template <typename S>
constexpr auto min = []() -> S { return std::numeric_limits<S>::min(); };
template <typename S>
constexpr auto max = []() -> S { return std::numeric_limits<S>::max(); };
template <typename S>
constexpr auto one_below_max = []() -> S { return std::numeric_limits<S>::max() - 1; };
template <typename S>
constexpr auto lowest = []() -> S { return std::numeric_limits<S>::lowest(); };
template <typename S>
constexpr auto one_above_lowest = []() -> S { return std::numeric_limits<S>::lowest() + 1; };
} // namespace element
namespace uoperator {
template <typename S>
constexpr auto identity = [](const S &val) -> S { return val; };
template <typename S>
constexpr auto negate = [](const S &val) -> S { return -val; };
} // namespace uoperator
namespace boperator {
template <typename T, typename S = T>
constexpr auto plus = [](const T &lhs, const S &rhs) -> S { return lhs + rhs; };
template <typename T, typename S = T>
constexpr auto mul = [](const T &lhs, const S &rhs) -> S { return lhs * rhs; };
template <typename T, typename S = T>
constexpr auto bit_and = [](const T &lhs, const S &rhs) -> S { return lhs & rhs; };
template <typename T, typename S = T>
constexpr auto bit_or = [](const T &lhs, const S &rhs) -> S { return lhs | rhs; };
template <typename T, typename S = T>
constexpr auto bit_xor = [](const T &lhs, const S &rhs) -> S { return lhs ^ rhs; };
template <typename T, typename S = T>
constexpr auto min = [](const T &lhs, const S &rhs) -> S { return std::min<S>(lhs, rhs); };
template <typename T, typename S = T>
constexpr auto max = [](const T &lhs, const S &rhs) -> S { return std::max<S>(lhs, rhs); };
template <typename T, typename S = T>
constexpr auto gcd = [](const T &lhs, const S &rhs) -> S { return std::gcd(lhs, rhs); };
template <typename T, typename S = T>
constexpr auto lcm = [](const T &lhs, const S &rhs) -> S { return std::lcm(lhs, rhs); };
template <typename F, auto id, typename X = F>
constexpr auto assign_if_not_id = [](const F &lhs, const X &rhs) -> X {
static_assert(std::is_invocable_r<F, decltype(id)>::value);
return (lhs == id() ? rhs : lhs);
};
} // namespace boperator
namespace monoid {
template <typename S>
using minimum = Monoid<S, boperator::min<S>, element::max<S>>;
template <typename S>
using minimum_safe = Monoid<S, boperator::min<S>, element::one_below_max<S>>;
template <typename S>
using maximum = Monoid<S, boperator::max<S>, element::lowest<S>>;
template <typename S>
using maximum_safe = Monoid<S, boperator::max<S>, element::one_above_lowest<S>>;
template <typename S>
using addition = Monoid<S, boperator::plus<S>, element::zero<S>>;
template <typename S>
using multiplication = Monoid<S, boperator::mul<S>, element::one<S>>;
template <typename S>
using bit_xor = Monoid<S, boperator::bit_xor<S>, element::zero<S>>;
} // namespace monoid
namespace group {
template <typename S>
using addition = Group<S, boperator::plus<S>, element::zero<S>, uoperator::negate<S>>;
template <typename S>
using bit_xor = Group<S, boperator::bit_xor<S>, element::zero<S>, uoperator::identity<S>>;
} // namespace group
namespace operator_monoid {
template <typename F, typename X = F>
using assign_for_minimum = OperatorMonoid<
F, boperator::assign_if_not_id<F, element::max<F>>, element::max<F>,
X, boperator::assign_if_not_id<F, element::max<F>, X>>;
template <typename F, typename X = F>
using assign_for_maximum = OperatorMonoid<
F, boperator::assign_if_not_id<F, element::lowest<F>>, element::lowest<F>,
X, boperator::assign_if_not_id<F, element::lowest<F>, X>>;
template <typename F, typename X = F>
using addition = OperatorMonoid<F, boperator::plus<F>, element::zero<F>, X, boperator::plus<F, X>>;
} // namespace operator_monoid
} // namespace algebra
} // namespace algorithm
#line 13 "algorithm/DataStructure/SegmentTree/binary_indexed_tree.hpp"
namespace algorithm {
namespace binary_indexed_tree {
template <class AbelianGroup>
class BIT {
public:
using group_type = AbelianGroup;
using value_type = group_type::value_type;
private:
int m_sz; // m_sz:=(要素数).
std::vector<group_type> m_tree;
static constexpr int lsb(int bit) { return bit & -bit; }
group_type sum_internal(int r) const {
group_type &&res = group_type::one();
for(; r >= 1; r -= lsb(r)) res = res * m_tree[r - 1];
return res;
}
void build() {
for(int i = 1; i < m_sz; ++i) {
int j = i + lsb(i);
if(j <= m_sz) m_tree[j - 1] = m_tree[j - 1] * m_tree[i - 1];
}
}
public:
// constructor. O(N).
BIT() : m_sz(0) {};
explicit BIT(int n) : m_sz(n), m_tree(n, group_type::one()) {
assert(n >= 0);
}
explicit BIT(int n, const value_type &a) : BIT(n, group_type(a)) {}
explicit BIT(int n, const group_type &a) : m_sz(n), m_tree(n, a) {
assert(n >= 0);
build();
}
template <std::input_iterator InputIter>
explicit BIT(InputIter first, InputIter last) : m_tree(first, last) {
m_sz = m_tree.size();
build();
}
template <typename T>
explicit BIT(std::initializer_list<T> il) : BIT(il.begin(), il.end()) {}
explicit BIT(const std::vector<group_type> &v) : m_sz(v.size()), m_tree(v) {
build();
}
explicit BIT(std::vector<group_type> &&v) : m_tree(std::move(v)) {
m_sz = m_tree.size();
build();
}
// 要素数を取得する．
int size() const { return m_sz; }
// k番目の要素をaとの積の結果に置き換える．O(log N).
void add(int k, const value_type &a) { add(k, group_type(a)); }
void add(int k, const group_type &a) {
assert(0 <= k and k < size());
for(int i = k + 1; i <= m_sz; i += lsb(i)) m_tree[i - 1] = m_tree[i - 1] * a;
}
// 区間[0,r)の要素の総積を求める．O(log N).
value_type sum(int r) const {
assert(0 <= r and r <= size());
return sum_internal(r).value();
}
// 区間[l,r)の要素の総積を求める．O(log N).
value_type sum(int l, int r) const {
assert(0 <= l and l <= r and r <= size());
return (sum_internal(r) * sum_internal(l).inv()).value();
}
// 全要素の総積を求める．O(log N).
value_type sum_all() const { return sum_internal(m_sz).value(); }
// pred(sum(r))==true となる区間の最右位値rを二分探索する．
// ただし，区間[0,n)の要素はpred(S)によって区分化されていること．また，pred(e)==true であること．O(log N).
template <bool (*pred)(value_type)>
int most_right() const {
return most_right([](const value_type &x) -> bool { return pred(x); });
}
template <typename Pred>
int most_right(Pred pred) const {
static_assert(std::is_invocable_r<bool, Pred, value_type>::value);
assert(pred(group_type::one().value()));
int r = 0;
group_type &&val = group_type::one();
for(int i = 1; i <= m_sz and pred(m_tree[i - 1].value()); i <<= 1) r = i, val = m_tree[i - 1];
for(int len = r >> 1; len > 0; len >>= 1) {
if(r + len <= m_sz and pred((val * m_tree[r + len - 1]).value())) {
r += len;
val = val * m_tree[r - 1];
}
}
return r;
}
void reset() { std::fill(m_tree.begin(), m_tree.end(), group_type::one()); }
};
template <typename S>
using range_sum_binary_indexed_tree = BIT<algebra::group::addition<S>>;
template <typename S>
using range_xor_binary_indexed_tree = BIT<algebra::group::bit_xor<S>>;
} // namespace binary_indexed_tree
} // namespace algorithm
#line 1 "algorithm/Graph/Tree/heavy_light_decomposition.hpp"
#line 8 "algorithm/Graph/Tree/heavy_light_decomposition.hpp"
namespace algorithm {
// Heavy-Light Decomposition（HL分解，重軽分解）.
class HLD {
int m_vn; // m_vn:=(ノード数).
std::vector<std::vector<int>> m_g; // m_g[v][]:=(ノードvの隣接リスト). グラフは森であること．
std::vector<int> m_par, m_head; // m_par[v]:=(ノードvの親番号), m_head[v]:=(ノードvを含むheavy pathの端点).
std::vector<int> m_sub; // m_sub[v]:=(ノードvを根とする部分木のサイズ).
std::vector<int> m_ord; // m_ord[v]:=(ノードvの行きかけ順序).
bool m_is_built;
bool is_built() const { return m_is_built; }
public:
// constructor. O(|V|).
HLD() : HLD(0) {}
explicit HLD(int vn) : m_vn(vn), m_g(vn), m_par(vn, -1), m_head(vn, -1), m_sub(vn, 1), m_ord(vn, -1), m_is_built(false) {
assert(vn >= 0);
}
// ノード数を取得する．
int order() const { return m_vn; }
// 無向辺を張る．
void add_edge(int u, int v) {
assert(0 <= u and u < order());
assert(0 <= v and v < order());
m_g[u].push_back(v);
m_g[v].push_back(u);
}
// 木をHL分解する．O(|V|).
void build() {
auto dfs = [&](auto self, int u, int p) -> int {
assert(m_par[u] == -1); // グラフに閉路はないこと．
m_par[u] = p, m_sub[u] = 1;
if(m_g[u].size() > 1 and m_g[u][0] == p) std::swap(m_g[u][0], m_g[u].back());
for(auto &v : m_g[u]) {
if(v == p) continue;
m_sub[u] += self(self, v, u);
if(m_sub[v] > m_sub[m_g[u][0]]) std::swap(m_g[u][0], v); // m_g[u][0]にheavy childを格納する．
}
return m_sub[u];
};
int next = 0;
auto dfs2 = [&](auto self, int u, int p) -> void {
m_ord[u] = next++;
for(auto v : m_g[u]) {
if(v == p) continue;
m_head[v] = (v == m_g[u][0] ? m_head[u] : v);
self(self, v, u);
}
};
std::fill(m_par.begin(), m_par.end(), -1);
for(int v = 0, end = order(); v < end; ++v) {
if(m_par[v] != -1) continue;
dfs(dfs, v, -1);
m_head[v] = v;
dfs2(dfs2, v, -1);
}
m_is_built = true;
}
// ノードvの行きがけ順序における番号を取得する．
int vertex_index(int v) const {
assert(0 <= v and v < order());
return m_ord[v];
}
const auto &vertex_index() const { return m_ord; }
// パスu-vにおける頂点属性のクエリに対応する範囲を求める．O(log|V|).
std::vector<std::pair<int, int>> vertex_query_ranges(int u, int v) const {
assert(0 <= u and u < order());
assert(0 <= v and v < order());
assert(is_built());
std::vector<std::pair<int, int>> res;
do {
if(m_ord[u] > m_ord[v]) std::swap(u, v);
if(m_head[u] == m_head[v]) {
res.emplace_back(m_ord[u], m_ord[v] + 1);
return res;
}
res.emplace_back(m_ord[m_head[v]], m_ord[v] + 1);
v = m_par[m_head[v]];
} while(v != -1);
return {}; // 非連結の場合．
}
// ノードvを根とする部分木における頂点属性のクエリに対応する範囲を求める．O(1).
std::pair<int, int> vertex_query_range_of_subtree(int v) const {
assert(0 <= v and v < order());
assert(is_built());
return {m_ord[v], m_ord[v] + m_sub[v]};
}
// 木上のノードuとvの最近共通祖先を求める．O(log|V|).
int lca(int u, int v) const {
assert(0 <= u and u < order());
assert(0 <= v and v < order());
assert(is_built());
do {
if(m_ord[u] > m_ord[v]) std::swap(u, v);
if(m_head[u] == m_head[v]) return u;
v = m_par[m_head[v]];
} while(v != -1);
return -1; // 非連結の場合．
}
};
} // namespace algorithm
#line 9 "verify/yosupo-vertex_add_subtree_sum-heavy_light_decomposition.test.cpp"
int main() {
int n;
int q;
std::cin >> n >> q;
std::vector<int> a(n);
for(auto &elem : a) std::cin >> elem;
algorithm::HLD hld(n);
for(int i = 1; i < n; ++i) {
int p;
std::cin >> p;
hld.add_edge(p, i);
}
hld.build();
using binary_indexed_tree = algorithm::binary_indexed_tree::range_sum_binary_indexed_tree<long long>;
using group = binary_indexed_tree::group_type;
std::vector<group> b(n);
for(int i = 0; i < n; ++i) b[hld.vertex_index()[i]] = a[i];
binary_indexed_tree bit(std::move(b));
while(q--) {
int t;
int u;
std::cin >> t >> u;
if(t == 0) {
int x;
std::cin >> x;
bit.add(hld.vertex_index(u), x);
} else {
auto &&[l, r] = hld.vertex_query_range_of_subtree(u);
auto &&ans = bit.sum(l, r);
std::cout << ans << "\n";
}
}
}