This documentation is automatically generated by online-judge-tools/verification-helper
View the Project on GitHub Harui-i/library
#define PROBLEM "https://judge.yosupo.jp/problem/vertex_add_path_sum" #include "template/template.hpp" #include <type_traits> #include <vector> 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]; HLD hld(N); for (int i=0; i<N-1; i++) { int u, v; cin >> u >> v; hld.graph.add_edge(u,v); hld.graph.add_edge(v,u); } 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 p, x; cin >> p >> x; fw.add(hld.id[p], x); } else if (op == 1) { int u, v; cin >> u >> v; ll ret = 0; for (Interval interval : hld.get_path(u, v)) { ret += fw.sum(interval.top_id, interval.bottom_id + 1); } cout << ret << endl; } } return 0; }
#line 1 "test/verify/yosupo-vertex-add-path-sum.test.cpp" #define PROBLEM "https://judge.yosupo.jp/problem/vertex_add_path_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-path-sum.test.cpp" #include <type_traits> #include <vector> 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" // 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>; struct HLD { //vector<vector<int>>children; std::vector<int>parent; std::vector<int> id; std::vector<int> id2; std::vector<int> head; std::vector<int>depth; 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); } 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] = (e == graph[v][0] ? head[v] : e.to); dfs_hld(e.to, k); } id2[v] = k; } int lca(int u, int v) { 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) { 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-path-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]; HLD hld(N); for (int i=0; i<N-1; i++) { int u, v; cin >> u >> v; hld.graph.add_edge(u,v); hld.graph.add_edge(v,u); } 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 p, x; cin >> p >> x; fw.add(hld.id[p], x); } else if (op == 1) { int u, v; cin >> u >> v; ll ret = 0; for (Interval interval : hld.get_path(u, v)) { ret += fw.sum(interval.top_id, interval.bottom_id + 1); } cout << ret << endl; } } return 0; }