library

This documentation is automatically generated by online-judge-tools/verification-helper

View the Project on GitHub Series-205/library

:heavy_check_mark: test/yosupo-vertex-add-path-sum.test.cpp

Depends on

Code

#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;
}
Back to top page