templates
This documentation is automatically generated by online-judge-tools/verification-helper
tests/tree/hld_path_query.test.cpp
- View this file on GitHub
- Last update: 2021-09-12 23:20:08-04:00
- Problem: https://judge.yosupo.jp/problem/vertex_add_path_sum
Depends on
template.hpp
Code
#define PROBLEM "https://judge.yosupo.jp/problem/vertex_add_path_sum"
#include "../../template.hpp"
#include "../test_utils.hpp"
#include "../../graph/edge_types.hpp"
#include "../../tree/hld.hpp"
#include "../../ds/bit.hpp"
struct CompLL {
using Data = ll;
const Data vdef = 0;
void applyUpdate(Data &to, Data &v) { to += v; }
int transformInd(int idx, int N) { return idx; }
};
const int MN = 5e5 + 1;
int N, Q;
ll A[MN];
vector<int> g[MN];
HLD<vector<int>[MN], Edge> hld;
BIT<CompLL> bit;
vector<int> &par = hld.par, &head = hld.head, &pos = hld.pos;
ll path(int u) {
ll res = 0;
while (u != -1) {
res += bit.query(pos[u]) - bit.query(pos[head[u]]-1);
u = par[head[u]];
}
return res;
}
int main() {
fast_io();
N = readi();
Q = readi();
for (int i = 1; i <= N; i++) A[i] = readi();
for (int i = 1; i <= N-1; i++) {
int a = readi()+1;
int b = readi()+1;
g[a].push_back(b);
g[b].push_back(a);
}
hld.init(N, g, 1);
bit.init(N);
for (int i = 1; i <= N; i++)
bit.update(pos[i], A[i]);
while (Q--) {
int t = readi();
int a = readi()+1;
int b = readi() + (t == 1);
if (t == 0) {
bit.update(pos[a], b);
A[a] += b;
}
else {
int l = hld.lca(a, b);
ll res = path(a) + path(b) - 2*path(l) + A[l];
print(res);
}
}
}#line 1 "tests/tree/hld_path_query.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/vertex_add_path_sum"
#line 2 "template.hpp"
#include <bits/stdc++.h>
#define DEBUG 1
using namespace std;
// Defines
#define fs first
#define sn second
#define pb push_back
#define eb emplace_back
#define mpr make_pair
#define mtp make_tuple
#define all(x) (x).begin(), (x).end()
// Basic type definitions
#if __cplusplus == 201703L // CPP17 only things
template <typename T> using opt_ref = optional<reference_wrapper<T>>; // for some templates
#endif
using ll = long long; using ull = unsigned long long; using ld = long double;
using pii = pair<int, int>; using pll = pair<long long, long long>;
#ifdef __GNUG__
// PBDS order statistic tree
#include <ext/pb_ds/assoc_container.hpp> // Common file
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
template <typename T, class comp = less<T>> using os_tree = tree<T, null_type, comp, rb_tree_tag, tree_order_statistics_node_update>;
template <typename K, typename V, class comp = less<K>> using treemap = tree<K, V, comp, rb_tree_tag, tree_order_statistics_node_update>;
// HashSet
#include <ext/pb_ds/assoc_container.hpp>
template <typename T, class Hash> using hashset = gp_hash_table<T, null_type, Hash>;
template <typename K, typename V, class Hash> using hashmap = gp_hash_table<K, V, Hash>;
const ll RANDOM = chrono::high_resolution_clock::now().time_since_epoch().count();
struct chash { ll operator()(ll x) const { return x ^ RANDOM; } };
#endif
// More utilities
int SZ(string &v) { return v.length(); }
template <typename C> int SZ(C &v) { return v.size(); }
template <typename C> void UNIQUE(vector<C> &v) { sort(v.begin(), v.end()); v.resize(unique(v.begin(), v.end()) - v.begin()); }
template <typename T, typename U> void maxa(T &a, U b) { a = max(a, b); }
template <typename T, typename U> void mina(T &a, U b) { a = min(a, b); }
const ll INF = 0x3f3f3f3f, LLINF = 0x3f3f3f3f3f3f3f3f;
#line 3 "tests/test_utils.hpp"
// I/O
template <typename T> void print(T v) {
cout << v << '\n';
}
template <typename T, typename... Rest> void print(T v, Rest... vs) {
cout << v << ' ';
print(vs...);
}
void fast_io() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
}
// Reading operators
template <typename T, typename U> istream& operator>>(istream& in, pair<T, U> &o) {
return in >> o.first >> o.second;
}
// Read helpers
int readi() {
int x; cin >> x;
return x;
}
ll readl() {
ll x; cin >> x;
return x;
}
template <typename T> vector<T> readv(int n) {
vector<T> res(n);
for (auto &x : res) cin >> x;
return res;
}
// Functional stuff
template <typename T> vector<pair<int, T>> enumerate(vector<T> v, int start = 0) {
vector<pair<int, T>> res;
for (auto &x : v)
res.emplace_back(start++, x);
return res;
}
#line 3 "graph/edge_types.hpp"
struct Edge {
using EdgeType = int;
int v(EdgeType e) { return e; }
int w(EdgeType e) { return 1; }
int i(EdgeType e) { throw domain_error("no information on edge indices"); }
EdgeType swapNode(EdgeType e, int v) { return v; }
};
template <typename T> struct WeightedEdge {
using EdgeType = pair<int, T>; using WeightType = T;
int v(EdgeType e) { return e.first; }
T w(EdgeType e) { return e.second; }
int i(EdgeType e) { throw domain_error("no information on edge indices"); }
EdgeType swapNode(EdgeType e, int v) { return {v, w(e)}; }
};
struct IndexedEdge {
using EdgeType = pair<int, int>;
int v(EdgeType e) { return e.first; }
int w(EdgeType e) { return 1; }
int i(EdgeType e) { return e.second; }
EdgeType swapNode(EdgeType e, int v) { return {v, i(e)}; }
};
template <typename T> struct WeightedIndexedEdge {
using EdgeType = tuple<int, T, int>; using WeightType = T;
int v(EdgeType e) { return get<0>(e); }
T w(EdgeType e) { return get<1>(e); }
int i(EdgeType e) { return get<2>(e); }
EdgeType swapNode(EdgeType e, int v) { return {v, w(e), i(e)}; }
};
#line 1 "tree/hld.hpp"
template <typename GraphType, typename EdgeType> struct HLD {
EdgeType E;
int cpos;
vector<int> par, dep, head, heavy, pos;
void init(int N, GraphType &g, int rt) {
cpos = 0;
par.assign(N + 1, 0); dep.assign(N + 1, 0); head.assign(N + 1, 0); heavy.assign(N + 1, -1); pos.assign(N + 1, 0);
function<int(int, int)> dfs = [&] (int c, int p) {
par[c] = p;
int sz = 1, mxsz = 0;
for (auto to : g[c]) {
int v = E.v(to);
if (v != p) {
dep[v] = dep[c] + 1;
int csz = dfs(v, c); sz += csz;
if (csz > mxsz) heavy[c] = v, mxsz = csz;
}
}
return sz;
};
function<void(int, int)> build = [&] (int c, int chead) {
pos[c] = ++cpos; head[c] = chead;
if (heavy[c] != -1) build(heavy[c], chead);
for (auto to : g[c]) {
int v = E.v(to);
if (v != par[c] && v != heavy[c])
build(v, v);
}
};
dfs(rt, -1);
build(rt, rt);
}
int lca(int a, int b) {
while (head[a] != head[b]) {
if (dep[head[a]] > dep[head[b]]) swap(a, b);
b = par[head[b]];
}
return dep[a] < dep[b] ? a : b;
}
#if __cplusplus == 201703L // CPP17 only things
void bind(opt_ref<vector<int>> par0, opt_ref<vector<int>> dep0, opt_ref<vector<int>> head0, opt_ref<vector<int>> heavy0, opt_ref<vector<int>> pos0) {
if (par0) par.swap(*par0);
if (dep0) dep.swap(*dep0);
if (head0) head.swap(*head0);
if (heavy0) heavy.swap(*heavy0);
if (pos0) pos.swap(*pos0);
}
#endif
};
#line 3 "ds/bit.hpp"
// Template is 1-indexed (by default). Can be made 0-indexed by modifying Comp
// Example: update = point increment, range sum
// In the function applyUpdate, updates are applied from `v` to `to`
struct Comp {
using Data = int;
const Data vdef = 0;
void applyUpdate(Data &to, Data &v) { to += v; }
int transformInd(int idx, int N) { return idx; }
};
template <typename Comp> struct BIT {
using Data = typename Comp::Data; Comp C;
int N; vector<Data> bit;
void init(int n0) {
N = n0;
bit.assign(N + 1, C.vdef);
}
void update(int x, Data v) {
x = C.transformInd(x, N);
for (; x <= N; x += x & -x)
C.applyUpdate(bit[x], v);
}
Data query(int x) {
x = C.transformInd(x, N);
Data res = C.vdef;
for (; x; x -= x & -x)
C.applyUpdate(res, bit[x]);
return res;
}
};
#line 7 "tests/tree/hld_path_query.test.cpp"
struct CompLL {
using Data = ll;
const Data vdef = 0;
void applyUpdate(Data &to, Data &v) { to += v; }
int transformInd(int idx, int N) { return idx; }
};
const int MN = 5e5 + 1;
int N, Q;
ll A[MN];
vector<int> g[MN];
HLD<vector<int>[MN], Edge> hld;
BIT<CompLL> bit;
vector<int> &par = hld.par, &head = hld.head, &pos = hld.pos;
ll path(int u) {
ll res = 0;
while (u != -1) {
res += bit.query(pos[u]) - bit.query(pos[head[u]]-1);
u = par[head[u]];
}
return res;
}
int main() {
fast_io();
N = readi();
Q = readi();
for (int i = 1; i <= N; i++) A[i] = readi();
for (int i = 1; i <= N-1; i++) {
int a = readi()+1;
int b = readi()+1;
g[a].push_back(b);
g[b].push_back(a);
}
hld.init(N, g, 1);
bit.init(N);
for (int i = 1; i <= N; i++)
bit.update(pos[i], A[i]);
while (Q--) {
int t = readi();
int a = readi()+1;
int b = readi() + (t == 1);
if (t == 0) {
bit.update(pos[a], b);
A[a] += b;
}
else {
int l = hld.lca(a, b);
ll res = path(a) + path(b) - 2*path(l) + A[l];
print(res);
}
}
}