cp-documentation

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

View the Project on GitHub zawa-tin/cp-documentation

:heavy_check_mark: Test/LC/vertex_add_subtree_sum.test.cpp

Depends on

Code

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

#include "../../Src/Template/IOSetting.hpp"
#include "../../Src/Graph/Tree/Sack.hpp"
#include "../../Src/Algebra/Group/AdditiveGroup.hpp"
#include "../../Src/DataStructure/FenwickTree/FenwickTree.hpp"

#include <cassert>
#include <iostream>
#include <utility>
#include <vector>

using namespace zawa;

int main() {
    SetFastIO();

    int n, q; std::cin >> n >> q;
    std::vector dat(n, std::vector<std::pair<int, long long>>{});
    for (int i{} ; i < n ; i++) {
        long long a; std::cin >> a;
        dat[i].emplace_back(0, a);
    }
    Sack sack(n);
    for (int i{1} ; i < n ; i++) {
        int p; std::cin >> p;
        sack.addEdge(p, i);
    }
    std::vector<long long> ans;
    ans.reserve(q);
    int id{};
    std::vector query(n, std::vector<std::pair<int, int>>{});
    query.reserve(q);
    for (int i{1} ; i <= q ; i++) {
        int t, v; std::cin >> t >> v;
        if (t == 0) {
            long long x; std::cin >> x;
            dat[v].emplace_back(i, x);
        }
        else if (t == 1) {
            ans.emplace_back(-1LL);
            query[v].emplace_back(i, id++);
        }
        else {
            assert(false);
        }
    }
    FenwickTree<AdditiveGroup<long long>> fen(q + 1);
    auto add{[&](int v) -> void {
        for (auto [time, x] : dat[v]) {
            fen.operation(time, x);
        }
    }};
    auto del{[&](int v) -> void {
        for (auto [time, x] : dat[v]) {
            fen.operation(time, -x);
        }
    }};
    auto answer{[&](int v) -> void {
        for (auto [time, i] : query[v]) {
            ans[i] = fen.prefixProduct(time + 1);
        }
    }};
    auto reset{[](){}};
    sack.execute(0, add, del, answer, reset);
    for (auto v : ans) {
        std::cout << v << '\n';
    }
}
#line 1 "Test/LC/vertex_add_subtree_sum.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/vertex_add_subtree_sum"

#line 2 "Src/Template/IOSetting.hpp"

#line 2 "Src/Template/TypeAlias.hpp"

#include <cstdint>
#include <cstddef>

namespace zawa {

using i16 = std::int16_t;
using i32 = std::int32_t;
using i64 = std::int64_t;
using i128 = __int128_t;

using u8 = std::uint8_t;
using u16 = std::uint16_t;
using u32 = std::uint32_t;
using u64 = std::uint64_t;

using usize = std::size_t;

} // namespace zawa
#line 4 "Src/Template/IOSetting.hpp"

#include <iostream>
#include <iomanip>

namespace zawa {

void SetFastIO() {
    std::cin.tie(nullptr)->sync_with_stdio(false);
}

void SetPrecision(u32 dig) {
    std::cout << std::fixed << std::setprecision(dig);
}

} // namespace zawa
#line 2 "Src/Graph/Tree/Sack.hpp"

#line 4 "Src/Graph/Tree/Sack.hpp"

#include <cassert>
#include <utility>
#include <vector>

namespace zawa {

class Sack {
private:    
    static constexpr u32 INVALID{static_cast<u32>(-1)};
    usize n_{};
    std::vector<std::vector<u32>> g_;
    std::vector<u32> sz_, euler_, L_, R_;

    u32 dfsHLD(u32 v, u32 p) {
        sz_[v] = 1;
        usize m{g_[v].size()};
        usize max{};
        if (m > 1u and g_[v][0] == p) std::swap(g_[v][0], g_[v][1]);
        for (u32 i{} ; i < m ; i++) if (g_[v][i] != p) {
            sz_[v] += dfsHLD(g_[v][i], v);
            if (max < sz_[g_[v][i]]) {
                max = sz_[g_[v][i]];
                if (i) std::swap(g_[v][0], g_[v][i]);
            }
        }
        return sz_[v];
    }

    void dfsEuler(u32 v, u32 p, u32& t) {
        euler_[t] = v;
        L_[v] = t++;
        for (auto x : g_[v]) if (x != p) {
            dfsEuler(x, v, t);
        }
        R_[v] = t;
    }

public:
    constexpr usize size() const noexcept {
        return n_;
    }

    Sack() = default;
    Sack(u32 n) 
        : n_{n}, g_(n), sz_(n), euler_(n), L_(n), R_(n) {
        assert(n);
        g_.shrink_to_fit();
        sz_.shrink_to_fit();
        euler_.shrink_to_fit();
        L_.shrink_to_fit();
        R_.shrink_to_fit();
    }
    void addEdge(u32 u, u32 v) {
        assert(u < size());
        assert(v < size());
        g_[u].emplace_back(v);
        g_[v].emplace_back(u);
    }

    const std::vector<u32>& operator[](u32 v) const noexcept {
        assert(v < size());
        return g_[v];
    }

    template <class ADD, class DEL, class QUERY, class RESET>
    u32 execute(u32 root, const ADD& add, const DEL& del, const QUERY& query, const RESET& reset) {
        dfsHLD(root, INVALID);
        u32 t{};
        dfsEuler(root, INVALID, t);
        
        auto sack{[&](auto dfs, u32 v, u32 p, bool keep) -> void {
            usize m{g_[v].size()};
            for (u32 i{1} ; i < m ; i++) if (g_[v][i] != p) {
                dfs(dfs, g_[v][i], v, false);
            }
            if (sz_[v] > 1u) dfs(dfs, g_[v][0], v, true);
            if (sz_[v] > 1u) {
                for (u32 i{R_[g_[v][0]]} ; i < R_[v] ; i++) {
                    add(euler_[i]);
                }
            }
            add(v);
            query(v);
            if (!keep) {
                for (u32 i{L_[v]} ; i < R_[v] ; i++) {
                    del(euler_[i]);
                }
                reset();
            }
        }};
        sack(sack, root, INVALID, false);

        return sz_[root];
    }
};

} // namespace zawa
#line 2 "Src/Algebra/Group/AdditiveGroup.hpp"

namespace zawa {

template <class T>
class AdditiveGroup {
public:
    using Element = T;
    static constexpr T identity() noexcept {
        return T{};
    }
    static constexpr T operation(const T& l, const T& r) noexcept {
        return l + r;
    }
    static constexpr T inverse(const T& v) noexcept {
        return -v;
    }
};

} // namespace zawa
#line 2 "Src/DataStructure/FenwickTree/FenwickTree.hpp"

#line 2 "Src/Algebra/Group/GroupConcept.hpp"

#line 2 "Src/Algebra/Monoid/MonoidConcept.hpp"

#line 2 "Src/Algebra/Semigroup/SemigroupConcept.hpp"

#include <concepts>

namespace zawa {

namespace concepts {

template <class T>
concept Semigroup = requires {
    typename T::Element;
    { T::operation(std::declval<typename T::Element>(), std::declval<typename T::Element>()) } -> std::same_as<typename T::Element>;
};

} // namespace concepts

} // namespace zawa
#line 4 "Src/Algebra/Monoid/MonoidConcept.hpp"

#line 6 "Src/Algebra/Monoid/MonoidConcept.hpp"

namespace zawa {

namespace concepts {

template <class T>
concept Identitiable = requires {
    typename T::Element;
    { T::identity() } -> std::same_as<typename T::Element>;
};

template <class T>
concept Monoid = Semigroup<T> and Identitiable<T>;

} // namespace

} // namespace zawa
#line 4 "Src/Algebra/Group/GroupConcept.hpp"

namespace zawa {

namespace concepts {

template <class T>
concept Inversible = requires {
    typename T::Element;
    { T::inverse(std::declval<typename T::Element>()) } -> std::same_as<typename T::Element>;
};

template <class T>
concept Group = Monoid<T> and Inversible<T>;

} // namespace Concept

} // namespace zawa
#line 5 "Src/DataStructure/FenwickTree/FenwickTree.hpp"

#line 8 "Src/DataStructure/FenwickTree/FenwickTree.hpp"
#include <ostream>
#include <functional>
#include <type_traits>

namespace zawa {

template <concepts::Group Group>
class FenwickTree {
public:

    using VM = Group;
    
    using V = typename VM::Element;

    FenwickTree() = default;

    explicit FenwickTree(usize n) : m_n{ n }, m_bitwidth{ std::__lg(n) + 1 }, m_a(n), m_dat(n + 1, VM::identity()) {
        m_dat.shrink_to_fit();
        m_a.shrink_to_fit();
    }

    explicit FenwickTree(const std::vector<V>& a) : m_n{ a.size() }, m_bitwidth{ std::__lg(a.size()) + 1 }, m_a(a), m_dat(a.size() + 1, VM::identity()) {
        m_dat.shrink_to_fit();  
        m_a.shrink_to_fit();
        for (i32 i{} ; i < static_cast<i32>(m_n) ; i++) {
            addDat(i, a[i]);
        }
    }

    inline usize size() const noexcept {
        return m_n;
    }

    // return a[i]
    const V& get(usize i) const noexcept {
        assert(i < size());
        return m_a[i];
    }

    // return a[i]
    const V& operator[](usize i) const noexcept {
        assert(i < size());
        return m_a[i];
    }

    // a[i] <- a[i] + v
    void operation(usize i, const V& v) {
        assert(i < size());
        addDat(i, v);
        m_a[i] = VM::operation(m_a[i], v);
    }

    // a[i] <- v
    void assign(usize i, const V& v) {
        assert(i < size());
        addDat(i, VM::operation(VM::inverse(m_a[i]), v));
        m_a[i] = v;
    }

    // return a[0] + a[1] + ... + a[r - 1]
    V prefixProduct(usize r) const {
        assert(r <= size());
        return product(r);
    }

    // return a[l] + a[l + 1] ... + a[r - 1]
    V product(usize l, usize r) const {
        assert(l <= r and r <= size());
        return VM::operation(VM::inverse(product(l)), product(r));
    }

    template <class Function>
    usize maxRight(usize l, const Function& f) const {
        static_assert(std::is_convertible_v<decltype(f), std::function<bool(V)>>, "maxRight's argument f must be function bool(T)");
        assert(l < size());
        V sum{ VM::inverse(product(l)) }; 
        usize r{};
        for (usize bit{ m_bitwidth } ; bit ; ) {
            bit--;
            usize nxt{ r | (1u << bit) };
            if (nxt < m_dat.size() and f(VM::operation(sum, m_dat[nxt]))) {
                sum = VM::operation(sum, m_dat[nxt]);
                r = std::move(nxt);
            }
        }
        assert(l <= r);
        return r;
    }

    template <class Function>
    usize minLeft(usize r, const Function& f) const {
        static_assert(std::is_convertible_v<decltype(f), std::function<bool(V)>>, "minLeft's argument f must be function bool(T)");
        assert(r <= size());
        V sum{ product(r) };
        usize l{};
        for (usize bit{ m_bitwidth } ; bit ; ) {
            bit--;
            usize nxt{ l | (1u << bit) };
            if (nxt <= r and not f(VM::operation(VM::inverse(m_dat[nxt]), sum))) {
                sum = VM::operation(VM::inverse(m_dat[nxt]), sum);
                l = std::move(nxt);
            }
        }
        assert(l <= r);
        return l;
    }

    // debug print
    friend std::ostream& operator<<(std::ostream& os, const FenwickTree& ft) {
        for (usize i{} ; i <= ft.size() ; i++) {
            os << ft.prefixProduct(i) << (i == ft.size() ? "" : " ");
        }
        return os;
    }

private:

    usize m_n{};

    usize m_bitwidth{};

    std::vector<V> m_a, m_dat;

    constexpr i32 lsb(i32 x) const noexcept {
        return x & -x;
    }
    
    // a[i] <- a[i] + v
    void addDat(i32 i, const V& v) {
        assert(0 <= i and i < static_cast<i32>(m_n));
        for ( i++ ; i < static_cast<i32>(m_dat.size()) ; i += lsb(i)) {
            m_dat[i] = VM::operation(m_dat[i], v);
        }
    }

    // return a[0] + a[1] + .. + a[i - 1]
    V product(i32 i) const {
        assert(0 <= i and i <= static_cast<i32>(m_n));
        V res{ VM::identity() };
        for ( ; i > 0 ; i -= lsb(i)) {
            res = VM::operation(res, m_dat[i]);
        }
        return res;
    }

};

} // namespace zawa
#line 7 "Test/LC/vertex_add_subtree_sum.test.cpp"

#line 12 "Test/LC/vertex_add_subtree_sum.test.cpp"

using namespace zawa;

int main() {
    SetFastIO();

    int n, q; std::cin >> n >> q;
    std::vector dat(n, std::vector<std::pair<int, long long>>{});
    for (int i{} ; i < n ; i++) {
        long long a; std::cin >> a;
        dat[i].emplace_back(0, a);
    }
    Sack sack(n);
    for (int i{1} ; i < n ; i++) {
        int p; std::cin >> p;
        sack.addEdge(p, i);
    }
    std::vector<long long> ans;
    ans.reserve(q);
    int id{};
    std::vector query(n, std::vector<std::pair<int, int>>{});
    query.reserve(q);
    for (int i{1} ; i <= q ; i++) {
        int t, v; std::cin >> t >> v;
        if (t == 0) {
            long long x; std::cin >> x;
            dat[v].emplace_back(i, x);
        }
        else if (t == 1) {
            ans.emplace_back(-1LL);
            query[v].emplace_back(i, id++);
        }
        else {
            assert(false);
        }
    }
    FenwickTree<AdditiveGroup<long long>> fen(q + 1);
    auto add{[&](int v) -> void {
        for (auto [time, x] : dat[v]) {
            fen.operation(time, x);
        }
    }};
    auto del{[&](int v) -> void {
        for (auto [time, x] : dat[v]) {
            fen.operation(time, -x);
        }
    }};
    auto answer{[&](int v) -> void {
        for (auto [time, i] : query[v]) {
            ans[i] = fen.prefixProduct(time + 1);
        }
    }};
    auto reset{[](){}};
    sack.execute(0, add, del, answer, reset);
    for (auto v : ans) {
        std::cout << v << '\n';
    }
}
Back to top page