cplib-cpp

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

View the Project on GitHub hitonanode/cplib-cpp

:heavy_check_mark: tree/test/vertex-add-subtree-sum.guni.test.cpp

Depends on

Code

#include "../../segmenttree/binary_indexed_tree.hpp"
#include "../guni.hpp"
#define PROBLEM "https://judge.yosupo.jp/problem/vertex_add_subtree_sum"
#include <cassert>
#include <iostream>
#include <vector>
using namespace std;

int main() {
    int N, Q;
    cin >> N >> Q;
    guni g(N);
    vector<int> A(N);
    for (auto &a : A) cin >> a;
    for (int i = 1; i < N; i++) {
        int p;
        cin >> p;
        g.add_bi_edge(p, i);
    }
    BIT<long long> bit(Q);
    vector<long long> ret(Q, -1);
    vector<vector<pair<int, int>>> v2t2add(N), v2t2sol(N);

    for (int i = 0; i < N; ++i) v2t2add.at(i).emplace_back(0, A.at(i));

    for (int t = 0; t < Q; ++t) {
        int tp, u;
        cin >> tp >> u;
        if (tp == 0) {
            int x;
            cin >> x;
            v2t2add.at(u).emplace_back(t, x);
        } else {
            v2t2sol.at(u).emplace_back(t, -1);
        }
    }

    auto Add = [&](int v) {
        for (auto [t, w] : v2t2add.at(v)) bit.add(t, w);
    };

    auto Remove = [&](int v) {
        for (auto [t, w] : v2t2add.at(v)) bit.add(t, -w);
    };

    auto Solve = [&](int v) {
        for (auto [t, _] : v2t2sol.at(v)) ret.at(t) = bit.sum(0, t + 1);
    };

    g.run(0, Add, Remove, Solve);

    for (auto x : ret) {
        if (x >= 0) cout << x << '\n';
    }
}
#line 2 "segmenttree/binary_indexed_tree.hpp"
#include <algorithm>
#include <vector>

// CUT begin
// 0-indexed BIT (binary indexed tree / Fenwick tree) (i : [0, len))
template <class T> struct BIT {
    int n;
    std::vector<T> data;
    BIT(int len = 0) : n(len), data(len) {}
    void reset() { std::fill(data.begin(), data.end(), T(0)); }
    void add(int pos, T v) { // a[pos] += v
        pos++;
        while (pos > 0 and pos <= n) data[pos - 1] += v, pos += pos & -pos;
    }
    T sum(int k) const { // a[0] + ... + a[k - 1]
        T res = 0;
        while (k > 0) res += data[k - 1], k -= k & -k;
        return res;
    }

    T sum(int l, int r) const { return sum(r) - sum(l); } // a[l] + ... + a[r - 1]

    template <class OStream> friend OStream &operator<<(OStream &os, const BIT &bit) {
        T prv = 0;
        os << '[';
        for (int i = 1; i <= bit.n; i++) {
            T now = bit.sum(i);
            os << now - prv << ',', prv = now;
        }
        return os << ']';
    }
};
#line 3 "tree/guni.hpp"

// Guni / Sack / DSU on tree
// https://codeforces.com/blog/entry/44351
struct guni {
    int n;
    int last_root;
    std::vector<std::vector<int>> to;
    std::vector<int> sz, ver, st, ft; // subtree size / dfs order / subtree start / subtree fin

    guni(int n_ = 0) : n(n_), last_root(-1), to(n_) {}

    void add_bi_edge(int u, int v) { to.at(u).push_back(v), to.at(v).push_back(u); }

    void sdfs(int v, int p) { // Build sz / ver / st / ft
        st.at(v) = ver.size(), ver.push_back(v);
        for (int u : to.at(v)) sz.at(v) += (u != p) ? (sdfs(u, v), sz.at(u)) : 0;
        ft.at(v) = ver.size();
    }

    template <class F1, class F2, class F3>
    void dfs(int v, int p, bool keep, F1 Add, F2 Remove, F3 Solve) {
        int mx = -1, big_child = -1;
        for (int u : to.at(v)) {
            if (u != p and sz.at(u) > mx) mx = sz.at(u), big_child = u;
        }
        for (int u : to.at(v)) {
            if (u != p and u != big_child) dfs(u, v, false, Add, Remove, Solve);
        }
        if (big_child != -1) dfs(big_child, v, true, Add, Remove, Solve);

        for (int u : to.at(v)) {
            if (u != p and u != big_child) {
                for (int i = st.at(u); i < ft.at(u); ++i) Add(ver.at(i));
            }
        }
        Add(v);
        Solve(v);

        if (!keep) {
            for (int i = st.at(v); i < ft.at(v); ++i) Remove(ver.at(i));
        }
    }

    template <class F1, class F2, class F3> void run(const int root, F1 Add, F2 Remove, F3 Solve) {
        if (last_root != root) {
            last_root = root, ver.clear(), st.resize(n), ft.resize(n), sz.assign(n, 1);
            sdfs(root, -1);
        }
        dfs(root, -1, false, Add, Remove, Solve);
    }
};
#line 3 "tree/test/vertex-add-subtree-sum.guni.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/vertex_add_subtree_sum"
#include <cassert>
#include <iostream>
#line 7 "tree/test/vertex-add-subtree-sum.guni.test.cpp"
using namespace std;

int main() {
    int N, Q;
    cin >> N >> Q;
    guni g(N);
    vector<int> A(N);
    for (auto &a : A) cin >> a;
    for (int i = 1; i < N; i++) {
        int p;
        cin >> p;
        g.add_bi_edge(p, i);
    }
    BIT<long long> bit(Q);
    vector<long long> ret(Q, -1);
    vector<vector<pair<int, int>>> v2t2add(N), v2t2sol(N);

    for (int i = 0; i < N; ++i) v2t2add.at(i).emplace_back(0, A.at(i));

    for (int t = 0; t < Q; ++t) {
        int tp, u;
        cin >> tp >> u;
        if (tp == 0) {
            int x;
            cin >> x;
            v2t2add.at(u).emplace_back(t, x);
        } else {
            v2t2sol.at(u).emplace_back(t, -1);
        }
    }

    auto Add = [&](int v) {
        for (auto [t, w] : v2t2add.at(v)) bit.add(t, w);
    };

    auto Remove = [&](int v) {
        for (auto [t, w] : v2t2add.at(v)) bit.add(t, -w);
    };

    auto Solve = [&](int v) {
        for (auto [t, _] : v2t2sol.at(v)) ret.at(t) = bit.sum(0, t + 1);
    };

    g.run(0, Add, Remove, Solve);

    for (auto x : ret) {
        if (x >= 0) cout << x << '\n';
    }
}
Back to top page