cp-library
This documentation is automatically generated by online-judge-tools/verification-helper
Test/Library Checker/Tree/vertex_add_path_sum01.test.cpp
- View this file on GitHub
- Last update: 2023-12-31 10:56:46+09:00
- Problem: https://judge.yosupo.jp/problem/vertex_add_path_sum
Depends on
- フェニック木 (BIT, Binary Indexed Tree)
(DataStructure/fenwick_tree.hpp)
- HL分解 (HLD, Heavy-Light-Decomposition)
(Tree/hld.hpp)
Code
#define PROBLEM "https://judge.yosupo.jp/problem/vertex_add_path_sum"
#include <bits/stdc++.h>
#include "Tree/hld.hpp"
#include "DataStructure/fenwick_tree.hpp"
using namespace std;
using ll = long long;
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
int N, Q, cmd, u, v;
cin >> N >> Q;
fenwick_tree<ll> fw(N);
vector<int> a(N);
vector<vector<int>> g(N);
for(auto &&v : a) cin >> v;
for(int i = 1; i < N; i++){
cin >> u >> v;
g[u].emplace_back(v);
g[v].emplace_back(u);
}
auto qf = [&](int l, int r){
return fw.sum(l, r);
};
auto f = [&](ll lhs, ll rhs){
return lhs + rhs;
};
Heavy_Light_Decomposition HLD(g);
for(int i = 0; i < N; i++){
fw.add(HLD[i], a[i]);
}
while(Q--){
cin >> cmd >> u >> v;
if(cmd == 0) fw.add(HLD[u], v);
else cout << HLD.query(u, v, 0ll, qf, f) << '\n';
}
}#line 1 "Test/Library Checker/Tree/vertex_add_path_sum01.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/vertex_add_path_sum"
#include <bits/stdc++.h>
#line 1 "Tree/hld.hpp"
struct Heavy_Light_Decomposition{
int N, tim = 0;
std::vector<int> sz, ent, leader, order, par;
std::vector<std::vector<int>> &G;
Heavy_Light_Decomposition(std::vector<std::vector<int>> &g) :
N(g.size()), G(g), sz(N), ent(N), leader(N), order(N), par(N) {
dfs_size(0, -1);
dfs_hld(0);
}
const int operator[](int v) const {
assert(0 <= v && v < N);
return ent[v];
}
int operator[](int v) {
assert(0 <= v && v < N);
return ent[v];
}
int la(int v, int k) {
while(true) {
int u = leader[v];
if(ent[v] - k >= ent[u]) return order[ent[v] - k];
k -= ent[v] - ent[u] + 1;
v = par[u];
}
}
int la(int from, int to, int d){
int d1 = 0, d2 = 0;
int v = from, u = to;
do{
if(ent[u] < ent[v]){
if(leader[u] == leader[v]){
d1 += ent[v] - ent[u];
break;
}
d1 += ent[v] - ent[leader[v]] + 1;
v = par[leader[v]];
}else{
if(leader[u] == leader[v]){
d2 += ent[u] - ent[v];
break;
}
d2 += ent[u] - ent[leader[u]] + 1;
u = par[leader[u]];
}
}while(true);
if(d > d1 + d2) return -1;
return d <= d1 ? la(from, d) : la(to, d1 + d2 - d);
}
int lca(int u, int v) {
do{
if(ent[u] > ent[v]) std::swap(u, v);
if(leader[u] == leader[v]) return u;
v = par[leader[v]];
}while(true);
}
int dist(int u, int v){
int ans = 0;
do{
if(ent[u] > ent[v]) std::swap(u, v);
if(leader[u] == leader[v]) return ans + ent[v] - ent[u];
ans += ent[v] - ent[leader[v]] + 1;
v = par[leader[v]];
}while(true);
}
template< typename T, typename Q, typename F >
T query(int u, int v, const T &identity, const Q &qf, const F &f, bool edge = false) {
T ans = identity;
do{
if(ent[u] > ent[v]) std::swap(u, v);
if(leader[u] == leader[v]) break;
ans = f( qf(ent[leader[v]], ent[v] + 1), ans);
v = par[leader[v]];
}while(true);
return f( qf(ent[u] + edge, ent[v] + 1), ans);
}
template< typename T, typename Q1, typename Q2, typename F >
T noncom_query(int u, int v, const T &identity,
const Q1 &qf, const Q2 &rev_qf, const F &f, bool edge = false) {
T sml = identity, smr = identity;
do{
if(leader[u] == leader[v]) break;
if(ent[u] < ent[v]){
smr = f( qf(ent[leader[v]], ent[v] + 1), smr);
v = par[leader[v]];
}else{
sml = f( sml, rev_qf(ent[leader[u]], ent[u] + 1));
u = par[leader[u]];
}
}while(true);
if(ent[u] < ent[v]){
return f(sml, f( qf(ent[u] + edge, ent[v] + 1), smr));
}else{
return f(f(sml, rev_qf(ent[v] + edge, ent[u] + 1)), smr);
}
}
template< typename Q >
void update(int u, int v, const Q &q, bool edge = false) {
do{
if(ent[u] > ent[v]) std::swap(u, v);
if(leader[u] == leader[v]) break;
q(ent[leader[v]], ent[v] + 1);
v = par[leader[v]];
}while(true);
q(ent[u] + edge, ent[v] + 1);
}
private:
void dfs_size(int v, int p){
par[v] = p;
sz[v] = 1;
if(!G[v].empty() && G[v][0] == p) std::swap(G[v][0], G[v].back());
for(auto &u : G[v]){
if(u == p) continue;
dfs_size(u, v);
sz[v] += sz[u];
if(sz[u] > sz[G[v][0]]) std::swap(G[v][0], u);
}
}
void dfs_hld(int v){
ent[v] = tim++;
order[ent[v]] = v;
for(auto &u : G[v]) {
if(u == par[v]) continue;
leader[u] = (G[v][0] == u ? leader[v] : u);
dfs_hld(u);
}
}
};
#line 1 "DataStructure/fenwick_tree.hpp"
template <class T> struct fenwick_tree {
using U = T;
public:
fenwick_tree() : _n(0) {}
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;
}
};
#line 6 "Test/Library Checker/Tree/vertex_add_path_sum01.test.cpp"
using namespace std;
using ll = long long;
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
int N, Q, cmd, u, v;
cin >> N >> Q;
fenwick_tree<ll> fw(N);
vector<int> a(N);
vector<vector<int>> g(N);
for(auto &&v : a) cin >> v;
for(int i = 1; i < N; i++){
cin >> u >> v;
g[u].emplace_back(v);
g[v].emplace_back(u);
}
auto qf = [&](int l, int r){
return fw.sum(l, r);
};
auto f = [&](ll lhs, ll rhs){
return lhs + rhs;
};
Heavy_Light_Decomposition HLD(g);
for(int i = 0; i < N; i++){
fw.add(HLD[i], a[i]);
}
while(Q--){
cin >> cmd >> u >> v;
if(cmd == 0) fw.add(HLD[u], v);
else cout << HLD.query(u, v, 0ll, qf, f) << '\n';
}
}