This documentation is automatically generated by online-judge-tools/verification-helper
View the Project on GitHub Series-205/library
#define PROBLEM "https://judge.yosupo.jp/problem/vertex_add_path_sum" #include <bits/stdc++.h> using namespace std; #include "../graph/heavy-light-decomposition.cpp" #include "../segtree/segment-tree.cpp" using ll = long long; using S = ll; S op(S l, S r) { return l + r; } S e() { return 0; } int main() { cin.tie(nullptr); ios::sync_with_stdio(false); int n, q; cin >> n >> q; vector<ll> a(n); for(int i = 0; i < n; i++) cin >> a[i]; HeavyLightDecomposition tree(n); for(int i = 0; i < n - 1; i++) { int u, v; cin >> u >> v; tree.add_edge(u, v); } tree.build(); vector<ll> b(n); for(int i = 0; i < n; i++) b[tree[i]] = a[i]; SegmentTree<S, op, e> seg(b); for(int i = 0; i < q; i++) { int t; cin >> t; if(t) { int u, v; cin >> u >> v; S res = e(); for(auto [l, r] : tree.node_query(u, v)) res = op(res, seg.prod(l, r)); cout << res << "\n"; } else { int p, x; cin >> p >> x; seg.set(tree[p], seg.get(tree[p]) + x); } } return 0; }
#line 1 "test/yosupo-vertex-add-path-sum.test.cpp" #define PROBLEM "https://judge.yosupo.jp/problem/vertex_add_path_sum" #include <bits/stdc++.h> using namespace std; #line 2 "graph/heavy-light-decomposition.cpp" #line 4 "graph/heavy-light-decomposition.cpp" using namespace std; class HeavyLightDecomposition { private: vector<vector<int>> g; vector<int> sz, in, out, head, rev, par; bool built; void dfs_sz(int v, int p) { par[v] = p; sz[v] = 1; if(!g[v].empty() && g[v][0] == p) swap(g[v][0], g[v].back()); for(auto &&u : g[v]) if(u != p) { dfs_sz(u, v); sz[v] += sz[u]; if(sz[u] > sz[g[v][0]]) swap(u, g[v][0]); } } void dfs_hld(int v, int p, int &t) { in[v] = t++; rev[in[v]] = v; for(auto &&u : g[v]) if(u != p) { head[u] = (u == g[v][0] ? head[v] : u); dfs_hld(u, v, t); } out[v] = t; } public: explicit HeavyLightDecomposition(int n) : g(n), sz(n), in(n), out(n), head(n), rev(n), par(n), built(false) {} explicit HeavyLightDecomposition(const vector<vector<int>> &g, int root = 0) : g(g), sz(g.size()), in(g.size()), out(g.size()), head(g.size()), rev(g.size()), par(g.size()) { build(root); } void add_edge(int u, int v) { g[u].push_back(v); g[v].push_back(u); } void build(int r = 0) { dfs_sz(r, -1); int t = 0; head[r] = r; dfs_hld(r, -1, t); built = true; } int lca(int u, int v) { assert(built); while(true) { if(in[u] > in[v]) swap(u, v); if(head[u] == head[v]) return u; v = par[head[v]]; } } pair<int, int> subtree_query(int u) { assert(built); return pair<int, int>{in[u], out[u]}; } vector<pair<int, int>> node_query(int u, int v) { assert(built); vector<pair<int, int>> res; while(true) { if(in[u] > in[v]) swap(u, v); if(head[u] == head[v]) break; res.emplace_back(in[head[v]], in[v] + 1); v = par[head[v]]; } res.emplace_back(in[u], in[v] + 1); return res; } vector<pair<int, int>> edge_query(int u, int v) { assert(built); vector<pair<int, int>> res; while(true) { if(in[u] > in[v]) swap(u, v); if(head[u] == head[v]) break; res.emplace_back(in[head[v]], in[v] + 1); v = par[head[v]]; } res.emplace_back(in[u] + 1, in[v] + 1); return res; } int operator[](int u) { assert(built); return in[u]; } }; /* * @brief Heavy-Light-Decomposition * @docs docs/heavy-light-decomposition.md */ #line 3 "segtree/segment-tree.cpp" using namespace std; // モノイド, 演算, 単位元 template <typename S, S (*op)(S, S), S (*e)()> class SegmentTree { private: int _n, sz; vector<S> data; void calc(int k) { data[k] = op(data[k << 1], data[k << 1 | 1]); } public: SegmentTree() = default; explicit SegmentTree(int n) : SegmentTree(vector<S>(n, e())) {} explicit SegmentTree(const vector<S>& v) : _n(v.size()) { sz = 1; while(sz < _n) sz <<= 1; data.assign(sz << 1, e()); for(int i = 0; i < _n; i++) data[sz + i] = v[i]; for(int i = sz - 1; i >= 1; i--) calc(i); } void set(int p, S x) { assert(0 <= p && p < _n); p += sz; data[p] = x; while(p >>= 1) calc(p); } S get(int p) { assert(0 <= p && p < _n); return data[p + sz]; } S prod(int l, int r) { assert(0 <= l && l <= r && r <= _n); S sl = e(), sr = e(); l += sz; r += sz; while(l < r) { if(l & 1) sl = op(sl, data[l++]); if(r & 1) sr = op(data[--r], sr); l >>= 1; r >>= 1; } return op(sl, sr); } S all_prod() { return data[1]; } }; /* * @brief Segment-Tree * @docs docs/segment-tree.md */ #line 8 "test/yosupo-vertex-add-path-sum.test.cpp" using ll = long long; using S = ll; S op(S l, S r) { return l + r; } S e() { return 0; } int main() { cin.tie(nullptr); ios::sync_with_stdio(false); int n, q; cin >> n >> q; vector<ll> a(n); for(int i = 0; i < n; i++) cin >> a[i]; HeavyLightDecomposition tree(n); for(int i = 0; i < n - 1; i++) { int u, v; cin >> u >> v; tree.add_edge(u, v); } tree.build(); vector<ll> b(n); for(int i = 0; i < n; i++) b[tree[i]] = a[i]; SegmentTree<S, op, e> seg(b); for(int i = 0; i < q; i++) { int t; cin >> t; if(t) { int u, v; cin >> u >> v; S res = e(); for(auto [l, r] : tree.node_query(u, v)) res = op(res, seg.prod(l, r)); cout << res << "\n"; } else { int p, x; cin >> p >> x; seg.set(tree[p], seg.get(tree[p]) + x); } } return 0; }