This documentation is automatically generated by online-judge-tools/verification-helper
View the Project on GitHub suisen-cp/cp-library-cpp
#define PROBLEM "https://judge.yosupo.jp/problem/vertex_add_path_sum" #include <iostream> #include <atcoder/segtree> #include "library/tree/euler_tour.hpp" using suisen::EulerTour; constexpr long long op(long long x, long long y) { return x + y; } constexpr long long e() { return 0LL; } int main() { std::ios::sync_with_stdio(false); std::cin.tie(nullptr); int n, q; std::cin >> n >> q; std::vector<long long> a(n); for (long long &e : a) std::cin >> e; std::vector<std::vector<int>> g(n); for (int i = 0; i < n - 1; ++i) { int u, v; std::cin >> u >> v; g[u].push_back(v); g[v].push_back(u); } EulerTour et(g); atcoder::segtree<long long, op, e> seg(2 * n); for (int i = 0; i < n; ++i) { seg.set(et.visit_time(i), +a[i]); seg.set(et.leave_time(i), -a[i]); } for (int i = 0; i < q; ++i) { int t; std::cin >> t; if (t == 0) { int p, x; std::cin >> p >> x; int l = et.visit_time(p), r = et.leave_time(p); seg.set(l, seg.get(l) + x); seg.set(r, seg.get(r) - x); } else { int u, v; std::cin >> u >> v; int a = et.lca(u, v); long long sum_au = seg.prod(et.visit_time(a), et.visit_time(u) + 1); long long sum_av = seg.prod(et.visit_time(a) + 1, et.visit_time(v) + 1); std::cout << sum_au + sum_av << '\n'; } } return 0; }
#line 1 "test/src/tree/euler_tour/vertex_add_path_sum.test.cpp" #define PROBLEM "https://judge.yosupo.jp/problem/vertex_add_path_sum" #include <iostream> #include <atcoder/segtree> #line 1 "library/tree/euler_tour.hpp" #include <limits> #include <vector> namespace suisen { /** * ImplicitGraph g : (int u, auto f) -> { for (int v : adjacent(u)) f(v); } */ class EulerTour { public: template <typename ImplicitGraph> EulerTour(const ImplicitGraph g, int n, int root = 0) : n(n), m(ceil_pow2(2 * n)) { dep.resize(n + 1), visit.resize(n), leave.resize(n); seg.assign(2 * m, n); dfs(g, root); for (int k = m - 1; k > 0; --k) seg[k] = argmin(seg[(k << 1) | 0], seg[(k << 1) | 1]); } template <typename Edge, typename EdgeToNode> EulerTour(const std::vector<std::vector<Edge>> &g, const EdgeToNode eton, int root = 0) : EulerTour([&](int u, auto f) { for (const Edge &e : g[u]) f(eton(e)); }, g.size(), root) {} EulerTour(const std::vector<std::vector<int>> &g, int root = 0) : EulerTour([&](int u, auto f) { for (int v : g[u]) f(v); }, g.size(), root) {} int lca(int u, int v) const { if (visit[u] > visit[v]) return lca(v, u); int res = n; for (int l = m + visit[u], r = m + visit[v] + 1; l < r; l >>= 1, r >>= 1) { if (l & 1) res = argmin(res, seg[l++]); if (r & 1) res = argmin(res, seg[--r]); } return res; } inline int dist(int u, int v) const { return dep[u] + dep[v] - 2 * dep[lca(u, v)]; } inline int depth(int u) const { return dep[u]; } inline int visit_time(int u) const { return visit[u]; } inline int leave_time(int u) const { return leave[u]; } inline int parent(int u) const { int p = seg[m + leave[u]]; return p == n ? -1 : p; } private: const int n, m; std::vector<int> visit, leave, dep, seg; template <typename ImplicitGraph> void dfs(ImplicitGraph g, int root) { dep[root] = 0, dep[n] = std::numeric_limits<int>::max(); int k = 0; auto f = [&](auto self, int u, int p) -> void { visit[u] = k, seg[m + k++] = u; g(u, [&](int v){ if (v != p) dep[v] = dep[u] + 1, self(self, v, u); }); leave[u] = k, seg[m + k++] = p; }; f(f, root, n); } inline int argmin(int u, int v) const { return dep[u] < dep[v] ? u : v; } static int ceil_pow2(const int n) { int k = 1; while (k < n) k <<= 1; return k; } }; } // namespace suisen #line 7 "test/src/tree/euler_tour/vertex_add_path_sum.test.cpp" using suisen::EulerTour; constexpr long long op(long long x, long long y) { return x + y; } constexpr long long e() { return 0LL; } int main() { std::ios::sync_with_stdio(false); std::cin.tie(nullptr); int n, q; std::cin >> n >> q; std::vector<long long> a(n); for (long long &e : a) std::cin >> e; std::vector<std::vector<int>> g(n); for (int i = 0; i < n - 1; ++i) { int u, v; std::cin >> u >> v; g[u].push_back(v); g[v].push_back(u); } EulerTour et(g); atcoder::segtree<long long, op, e> seg(2 * n); for (int i = 0; i < n; ++i) { seg.set(et.visit_time(i), +a[i]); seg.set(et.leave_time(i), -a[i]); } for (int i = 0; i < q; ++i) { int t; std::cin >> t; if (t == 0) { int p, x; std::cin >> p >> x; int l = et.visit_time(p), r = et.leave_time(p); seg.set(l, seg.get(l) + x); seg.set(r, seg.get(r) - x); } else { int u, v; std::cin >> u >> v; int a = et.lca(u, v); long long sum_au = seg.prod(et.visit_time(a), et.visit_time(u) + 1); long long sum_av = seg.prod(et.visit_time(a) + 1, et.visit_time(v) + 1); std::cout << sum_au + sum_av << '\n'; } } return 0; }