test/yosupo/tree/vertex_add_path_sum_hld.test.cpp

• View this file on GitHub
• Last update: 2025-09-25 11:45:13+07:00
• Problem: https://judge.yosupo.jp/problem/vertex_add_path_sum

Depends on

• Segment Tree (ds/segtree.hpp)
• other/types.hpp
• other/update_proxy.hpp
• Heavy-light Decomposition (tree/hld.hpp)

Code

#define PROBLEM "https://judge.yosupo.jp/problem/vertex_add_path_sum"

#include <bits/stdc++.h>
using namespace std;

#include "ds/segtree.hpp"
#include "tree/hld.hpp"
#include "other/types.hpp"

struct M {
    using T = i64;
    static T id() { return 0; };
    static T op(T l, T r) { return l + r; }
};

int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    int n, q;
    cin >> n >> q;
    vector<int> a(n);
    vector<basic_string<int>> g(n);

    for (int &i : a) cin >> i;
    for (int i = 0, u, v; i < n - 1; i++) {
        cin >> u >> v;
        g[u] += v, g[v] += u;
    }
    HLD hld(g);
    vector<int> inv(n);
    for (int i = 0; i < n; i++) inv[hld[i]] = i;
    SegTree<M> st(n, [&](int i) { return a[inv[i]]; });

    while (q--) {
        int t, p, x, u, v;
        cin >> t;
        if (t == 0) {
            cin >> p >> x;
            st[hld[p]] += x;
        } else {
            cin >> u >> v;
            int w = hld.lca(u, v);
            i64 sm = 0;
            for (auto [l, r] : hld.path(u, w)) sm += st(l, r);
            for (auto [l, r] : hld.path(v, w, 1)) sm += st(l, r);
            cout << sm << "\n";
        }
    }
}

#line 1 "test/yosupo/tree/vertex_add_path_sum_hld.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/vertex_add_path_sum"

#include <bits/stdc++.h>
using namespace std;

#line 2 "ds/segtree.hpp"

#line 2 "other/update_proxy.hpp"

// clang-format off
template<class T, class Cb> struct UpdateProxy {
    T &x;
    Cb cb;

    UpdateProxy(T &_x, Cb _cb) : x(_x), cb(_cb) {}

    operator const T &() const { return x; }
    auto &operator*() && { return x; }
    auto operator->() && { return &x; }
    auto operator++(int) && { T old = x; return ++x, cb(), old; }
    auto operator--(int) && { T old = x; return --x, cb(), old; }
    auto &operator++() && { ++x, cb(); return *this; }
    auto &operator--() && { --x, cb(); return *this; }
    auto &operator+=(const T &r) && { x += r, cb(); return *this; }
    auto &operator-=(const T &r) && { x -= r, cb(); return *this; }
    auto &operator*=(const T &r) && { x *= r, cb(); return *this; }
    auto &operator/=(const T &r) && { x /= r, cb(); return *this; }
    auto &operator%=(const T &r) && { x %= r, cb(); return *this; }
    auto &operator=(const T &r) && { x = r, cb(); return *this; }
    auto &operator<<=(const T &r) && { x <<= r, cb(); return *this; }
    auto &operator>>=(const T &r) && { x >>= r, cb(); return *this; }
    template<class F> auto &apply(F &&f) && { f(x), cb(); return *this; }
};
// clang-format on
#line 4 "ds/segtree.hpp"

// Modified version of atcoder library's segtree.hpp
template<class M> struct SegTree {
    using T = typename M::T;

    int n, m;
    vector<T> t;

    SegTree() = default;
    SegTree(int _n) : n(_n), m(bit_ceil(n)), t(2 * m, M::id()) {}
    template<class G> SegTree(int _n, G &&gen) : SegTree(_n) {
        for (int i = 0; i < n; i++) t[i + m] = gen(i);
        for (int i = m; --i;) update(i);
    }
    template<class V>
    SegTree(const V &v) :
        SegTree((int)v.size(), [&](int i) { return T(v[i]); }) {}

    vector<T> to_vec() {
        vector<T> r(n);
        for (int i = 0; i < n; i++) r[i] = t[i + m];
        return r;
    }
    void set(int p, const T &x) {
        assert(0 <= p && p < n);
        t[p + m] = x, update_from(p);
    }
    void mul(int p, const T &x) {
        assert(0 <= p && p < n);
        t[p + m] = M::op(t[p + m], x), update_from(p);
    }
    auto operator[](int p) {
        assert(0 <= p && p < n);
        UpdateProxy up(t[p + m], [this, p]() { update_from(p); });
        return up;
    }
    T operator[](int p) const {
        assert(0 <= p && p < n);
        return t[p + m];
    }
    T get(int p) const { return (*this)[p]; }
    T operator()(int l, int r) const {
        assert(0 <= l && l <= r && r <= n);
        T resl = M::id(), resr = M::id();
        for (l += m, r += m; l < r; l >>= 1, r >>= 1) {
            if (l & 1) resl = M::op(resl, t[l++]);
            if (r & 1) resr = M::op(t[--r], resr);
        }
        return M::op(resl, resr);
    }
    T pref(int r) const { return (*this)(0, r); }
    T suff(int l) const { return (*this)(l, n); }
    T prod(int l, int r) const { return (*this)(l, r); }
    T all_prod() const { return t[1]; }
    template<class G> int max_right(int l, G &&g) const {
        assert(0 <= l && l <= n);
        assert(g(M::id()));
        if (l == n) return n;
        l += m;
        T sm = M::id();
        do {
            for (; l % 2 == 0; l >>= 1);
            if (!g(M::op(sm, t[l]))) {
                while (l < m) {
                    l = l << 1;
                    if (g(M::op(sm, t[l]))) sm = M::op(sm, t[l++]);
                }
                return l - m;
            }
            sm = M::op(sm, t[l++]);
        } while ((l & -l) != l);
        return n;
    }
    template<class G> int min_left(int r, G &&g) const {
        assert(0 <= r && r <= n);
        assert(g(M::id()));
        if (r == 0) return 0;
        r += m;
        T sm = M::id();
        do {
            for (r--; r > 1 && r & 1; r >>= 1);
            if (!g(M::op(t[r], sm))) {
                while (r < m) {
                    r = r << 1 | 1;
                    if (g(M::op(t[r], sm))) sm = M::op(t[r--], sm);
                }
                return r + 1 - m;
            }
            sm = M::op(t[r], sm);
        } while ((r & -r) != r);
        return 0;
    }

  private:
    // clang-format off
    static int bit_ceil(int n) { int m = 1; while (m < n) m *= 2; return m; }
    // clang-format on
    void update(int p) { t[p] = M::op(t[p << 1], t[p << 1 | 1]); }
    void update_from(int p) {
        for (p += m; p >>= 1;) update(p);
    }
};
#line 2 "tree/hld.hpp"

struct HLD {
    int n;
    vector<int> in, par, dep, out, hs;

    template<class G>
    HLD(G &g, int root = 0) :
        n((int)g.size()), in(n), par(n), dep(n), out(n), hs(n) {
        hs[root] = root;
        dfs_sz(g, root);
        dfs_hld(g, root);
        assert(time == n);
    }

    int lca(int u, int v) const {
        assert(0 <= u && u < n && 0 <= v && v < n);
        for (;; v = par[hs[v]]) {
            if (in[u] > in[v]) swap(u, v);
            if (hs[u] == hs[v]) return u;
        }
    }
    int dist(int u, int v) const {
        assert(0 <= u && u < n);
        assert(0 <= v && v < n);
        return dep[u] + dep[v] - 2 * dep[lca(u, v)];
    }
    auto path(int v, int p, bool es = 0) const {
        assert(in[p] <= in[v] && out[v] <= out[p]);
        vector<pair<int, int>> res;
        for (; hs[v] != hs[p]; v = par[hs[v]])
            res.emplace_back(in[hs[v]], in[v] + 1);
        res.emplace_back(in[p] + es, in[v] + 1);
        return res;
    }
    pair<int, int> subtree(int v) const {
        assert(0 <= v && v < n);
        return {in[v], out[v]};
    }
    int operator[](int v) { return in[v]; }
    int operator()(int v) { return out[v]; }

  private:
    int time = 0;
    template<class G> int dfs_sz(G &g, int v, int p = -1) {
        par[v] = p;
        int sz = 1, mx = 0;
        for (auto &c : g[v]) {
            if (c == p) continue;
            dep[c] = dep[v] + 1;
            int s = dfs_sz(g, c, v);
            sz += s;
            if (g[v][0] == p || mx < s) mx = s, swap(g[v][0], c);
        }
        return sz;
    }
    template<class G> void dfs_hld(G &g, int v, int p = -1) {
        in[v] = time++;
        for (auto c : g[v]) {
            if (c == p) continue;
            hs[c] = (c == g[v][0] ? hs[v] : c);
            dfs_hld(g, c, v);
        }
        out[v] = time;
    }
};
#line 2 "other/types.hpp"

using i8 = int8_t;
using u8 = uint8_t;
using i32 = int32_t;
using u32 = uint32_t;
using i64 = int64_t;
using u64 = uint64_t;
using f32 = float;
using f64 = double;
using f80 = long double;
using str = string;
template<class T> using vec = vector<T>;
template<class E = i32> using graph = vec<vec<E>>;
#line 9 "test/yosupo/tree/vertex_add_path_sum_hld.test.cpp"

struct M {
    using T = i64;
    static T id() { return 0; };
    static T op(T l, T r) { return l + r; }
};

int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    int n, q;
    cin >> n >> q;
    vector<int> a(n);
    vector<basic_string<int>> g(n);

    for (int &i : a) cin >> i;
    for (int i = 0, u, v; i < n - 1; i++) {
        cin >> u >> v;
        g[u] += v, g[v] += u;
    }
    HLD hld(g);
    vector<int> inv(n);
    for (int i = 0; i < n; i++) inv[hld[i]] = i;
    SegTree<M> st(n, [&](int i) { return a[inv[i]]; });

    while (q--) {
        int t, p, x, u, v;
        cin >> t;
        if (t == 0) {
            cin >> p >> x;
            st[hld[p]] += x;
        } else {
            cin >> u >> v;
            int w = hld.lca(u, v);
            i64 sm = 0;
            for (auto [l, r] : hld.path(u, w)) sm += st(l, r);
            for (auto [l, r] : hld.path(v, w, 1)) sm += st(l, r);
            cout << sm << "\n";
        }
    }
}

Test cases

Env	Name	Status	Elapsed	Memory
g++	almost_line_00	AC	339 ms	59 MB
g++	almost_line_01	AC	336 ms	57 MB
g++	example_00	AC	4 ms	4 MB
g++	line_00	AC	333 ms	56 MB
g++	line_01	AC	327 ms	63 MB
g++	long-path-decomposition_killer_00	AC	230 ms	41 MB
g++	max_random_00	AC	393 ms	44 MB
g++	max_random_01	AC	386 ms	44 MB
g++	max_random_02	AC	382 ms	44 MB
g++	random_00	AC	300 ms	37 MB
g++	random_01	AC	327 ms	42 MB
g++	random_02	AC	171 ms	8 MB
g++	random_03	AC	131 ms	39 MB
g++	random_04	AC	125 ms	30 MB
g++	small_00	AC	5 ms	4 MB
g++	small_01	AC	4 ms	4 MB
g++	small_02	AC	4 ms	4 MB
g++	small_03	AC	4 ms	4 MB
g++	small_04	AC	4 ms	4 MB
clang++	almost_line_00	AC	378 ms	74 MB
clang++	almost_line_01	AC	379 ms	70 MB
clang++	example_00	AC	4 ms	4 MB
clang++	line_00	AC	369 ms	69 MB
clang++	line_01	AC	384 ms	83 MB
clang++	long-path-decomposition_killer_00	AC	233 ms	41 MB
clang++	max_random_00	AC	442 ms	44 MB
clang++	max_random_01	AC	449 ms	44 MB
clang++	max_random_02	AC	443 ms	44 MB
clang++	random_00	AC	346 ms	37 MB
clang++	random_01	AC	379 ms	42 MB
clang++	random_02	AC	196 ms	8 MB
clang++	random_03	AC	137 ms	39 MB
clang++	random_04	AC	136 ms	30 MB
clang++	small_00	AC	5 ms	4 MB
clang++	small_01	AC	4 ms	4 MB
clang++	small_02	AC	4 ms	4 MB
clang++	small_03	AC	4 ms	4 MB
clang++	small_04	AC	4 ms	4 MB

Back to top page