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_range_contour_sum_on_tree.test.cpp

Depends on

Code

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

#include "../../Src/Graph/Tree/ContourAggregation.hpp"
#include "../../Src/DataStructure/FenwickTree/FenwickTree.hpp"
#include "../../Src/Algebra/Group/AdditiveGroup.hpp"
using namespace zawa;

#include <cassert>
#include <iostream>
#include <vector>
using namespace std;

int main() {
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(0);
    int N, Q;
    cin >> N >> Q;
    vector<int> A(N);
    for (auto& x : A)
        cin >> x;
    vector<vector<int>> G(N);
    for (int i = 0 ; i < N - 1 ; i++) {
       int u, v;
       cin >> u >> v;
       G[u].push_back(v);
       G[v].push_back(u);
    }
    ContourAggregation sol(move(G));
    cerr << "size=" << ssize(sol) << endl;
    FenwickTree<AdditiveGroup<long long>> fen(ssize(sol));
    for (int i = 0 ; i < N ; i++) 
        for (int j : sol.point(i))
            fen.operation(j,A[i]);
    while (Q--) {
        int T;
        cin >> T;
        if (T == 0) {
            int p, x;
            cin >> p >> x;
            for (int i : sol.point(p))
                fen.operation(i,x);
        }
        else if (T == 1) {
            int p, l, r;
            cin >> p >> l >> r;
            // cout << "query " << p << ' ' << l << ' ' << r << endl;
            long long ans = 0;
            for (auto [L, R] : sol.contour(p,l,r))
                ans += fen.product(L,R);
            cout << ans << '\n';
        }
        else
            assert(0);
    }
}
#line 1 "Test/LC/vertex_add_range_contour_sum_on_tree.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/vertex_add_range_contour_sum_on_tree"

#line 2 "Src/Graph/Tree/ContourAggregation.hpp"

#line 2 "Src/Graph/Tree/Centroid.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/Graph/Tree/Centroid.hpp"

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

namespace zawa {

template <class V>
class Centroid {
public:

    Centroid() = default;

    Centroid(const std::vector<std::vector<V>>& T) : T_{T}, size_(T_.size(), usize{1}) {}
    Centroid(std::vector<std::vector<V>>&& T) : T_{std::move(T)}, size_(T_.size(), usize{1}) {}

    inline usize size() const noexcept {
        return T_.size();
    }

    inline usize size(V v) const noexcept {
        assert(v < (V)size());
        return size_[v];
    }

    bool isRemoved(V v) const noexcept {
        assert(v < (V)size());
        return size_[v] == 0u;
    }

    void remove(V v) noexcept {
        assert(v < (V)size());
        size_[v] = 0u;
    }

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

    // @response: centroid of component which v belongs
    V rooting(V v) {
        assert(v < (V)size());
        assert(!isRemoved(v));
        usize all{dfsSize(v, INVALID)};
        V par{INVALID};
        bool fn{false};
        while (!fn) {
            fn = true;
            for (V x : T_[v]) {
                if (x == par or isRemoved(x) or usize{2} * size_[x] <= all) {
                    continue;
                }
                fn = false;
                par = v;
                v = x;
                break;
            }
        }
        return v;
    }

    std::vector<V> component(V v) const {
        assert(v < (V)size());
        assert(!isRemoved(v));
        std::vector<V> res;
        dfsComponent(v, INVALID, res);
        return res;
    }

    std::vector<V> adjlist(V v) const {
        assert(v < (V)size());
        std::vector<V> res;
        res.reserve(T_[v].size());
        for (auto x : T_[v]) if (!isRemoved(x)) {
            res.emplace_back(x);
        }
        return res;
    }

private:
    static constexpr V INVALID{static_cast<V>(-1)};
    std::vector<std::vector<V>> T_{};
    std::vector<usize> size_{};

    usize dfsSize(V v, V par) {
        size_[v] = 1u;
        for (V x : T_[v]) if (x != par and !isRemoved(x)) {
            size_[v] += dfsSize(x, v);
        }
        return size_[v];
    }

    void dfsComponent(V v, V par, std::vector<V>& comp) const {
        comp.emplace_back(v);
        for (V x : T_[v]) if (x != par and !isRemoved(x)) {
            dfsComponent(x, v, comp);
        }
    }
};

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

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

#line 4 "Src/Algebra/Monoid/ChminMonoid.hpp"

#include <algorithm>
#include <optional>

namespace zawa {

template <class T, class U>
class ChminMonoidData {
private:
    std::optional<T> priority_{};
    U value_{};
public:
    ChminMonoidData() = default;
    ChminMonoidData(const U& value)
        : priority_{std::nullopt}, value_{value} {}
    ChminMonoidData(const T& priority, const U& value)
        : priority_{priority}, value_{value} {}

    constexpr bool infty() const noexcept {
        return !priority_.has_value();
    }
    constexpr const T& priority() const noexcept {
        return priority_.value();
    }
    constexpr const U& value() const noexcept {
        return value_;
    }
    friend constexpr bool operator<(const ChminMonoidData& l, const ChminMonoidData& r) {
        if (l.infty()) return false;
        else if (r.infty()) return true;
        else return l.priority() < r.priority();
    }
};

template <class T, class U>
struct ChminMonoid {
    using Element = ChminMonoidData<T, U>;
    static Element identity() noexcept {
        return Element{};
    }
    static Element operation(const Element& l, const Element& r) noexcept {
        return (r < l ? r : l);
    }
};

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

#line 4 "Src/DataStructure/SparseTable/SparseTable.hpp"

#line 7 "Src/DataStructure/SparseTable/SparseTable.hpp"
#include <ostream>

namespace zawa {

template <class Structure>
class SparseTable {
private:
    using Value = typename Structure::Element;
    std::vector<u32> L;
    std::vector<std::vector<Value>> dat;
public:

    SparseTable() : L{}, dat{} {}
    SparseTable(const std::vector<Value>& a) : L(a.size() + 1), dat{} {
        for (u32 i{1} ; i < L.size() ; i++) {
            L[i] = L[i - 1] + (i >> (L[i - 1] + 1));
        }
        dat.resize(L.back() + 1);
        dat[0] = a;
        for (u32 i{1}, len{2} ; i < dat.size() ; i++, len <<= 1) {
            dat[i] = dat[i - 1];
            for (u32 j{} ; j + len - 1 < dat[i].size() ; j++) {
                dat[i][j] = Structure::operation(dat[i - 1][j], dat[i - 1][j + (len >> 1)]);
            }
        }
    }

    Value product(u32 l, u32 r) const {
        assert(l <= r);
        assert(l < dat[0].size());
        assert(r <= dat[0].size());
        u32 now{L[r - l]};
        return Structure::operation(dat[now][l], dat[now][r - (1 << now)]);
    }

    friend std::ostream& operator<<(std::ostream& os, const SparseTable<Structure>& spt) {
        for (u32 i{}, len{1} ; i < spt.dat.size() ; i++, len <<= 1) {
            os << "length = " << len << '\n';
            for (u32 j{} ; j + len - 1 < spt.dat[i].size() ; j++) {
                os << spt.dat[i][j] << (j + len == spt.dat[i].size() ? '\n' : ' ');
            }
        }
        return os;
    }
};

} // namespace zawa
#line 6 "Src/Graph/Tree/LowestCommonAncestor.hpp"

#line 9 "Src/Graph/Tree/LowestCommonAncestor.hpp"

namespace zawa {

template <class V>
class LowestCommonAncestor {
private:
    using Monoid = ChminMonoid<u32, V>;

public:
    LowestCommonAncestor() = default;

    LowestCommonAncestor(const std::vector<std::vector<V>>& tree, V r = V{}) 
        : n_{tree.size()}, depth_(tree.size()), L_(tree.size()), R_(tree.size()), st_{} {
            std::vector<typename Monoid::Element> init;
            init.reserve(2 * size());
            auto dfs{[&](auto dfs, V v, V p) -> void {
                depth_[v] = (p == INVALID ? 0u : depth_[p] + 1);
                L_[v] = (u32)init.size();
                for (auto x : tree[v]) {
                    if (x == p) {
                        continue;
                    }
                    init.emplace_back(depth_[v], v);
                    dfs(dfs, x, v);
                }
                R_[v] = (u32)init.size();
            }};
            dfs(dfs, r, INVALID);
            st_ = SparseTable<Monoid>(init);
    }

    V operator()(V u, V v) const {
        assert(verify(u));
        assert(verify(v));
        if (L_[u] > L_[v]) {
            std::swap(u, v);
        }
        return u == v ? u : st_.product(L_[u], R_[v]).value();
    }

    V lca(V u, V v) const {
        return (*this)(u, v);
    }

    inline u32 depth(V v) const noexcept {
        assert(verify(v));
        return depth_[v];
    }

    u32 distance(V u, V v) const {
        assert(verify(u));
        assert(verify(v));
        return depth(u) + depth(v) - 2u * depth((*this)(u, v));
    }

    bool isAncestor(V p, V v) const {
        assert(verify(p));
        assert(verify(v));
        return L_[p] <= L_[v] and R_[v] <= R_[p];
    }

protected:
    u32 left(V v) const noexcept {
        return L_[v];
    }

    inline usize size() const {
        return n_;
    }

    inline bool verify(V v) const {
        return v < (V)size();
    }

private:
    static constexpr V INVALID{static_cast<V>(-1)};
    usize n_{};
    std::vector<u32> depth_, L_, R_;
    SparseTable<Monoid> st_;
};

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

#line 4 "Src/DataStructure/Heap/BinaryHeap.hpp"

#line 7 "Src/DataStructure/Heap/BinaryHeap.hpp"
#include <concepts>
#line 10 "Src/DataStructure/Heap/BinaryHeap.hpp"
#include <functional>

namespace zawa {

template <class T, class Comp = std::less<T>>
requires std::strict_weak_order<Comp, const T&, const T&>
class BinaryHeap {
private:

    Comp m_comp;

    std::vector<T> m_dat;

public:

    inline usize size() const {
        return m_dat.size() - 1;
    }

    inline bool empty() const {
        return m_dat.size() == 1;
    }

    inline const Comp& comp() const {
        return m_comp;
    }

    using const_iterator = typename decltype(m_dat)::const_iterator;

    const_iterator begin() const {
        return m_dat.begin() + 1;
    }

    const_iterator end() const {
        return m_dat.end();
    }

    BinaryHeap(Comp comp = {}) 
        : m_comp{comp}, m_dat(1) {}

    template <std::forward_iterator It>
    requires std::same_as<std::iter_value_t<It>, T>
    BinaryHeap(It first, It last, Comp comp = {}) 
        : m_comp{comp}, m_dat(1) {
        m_dat.insert(m_dat.end(), first, last);
        build();
    }

    BinaryHeap(std::vector<T>&& a, Comp comp = {}) 
        : m_comp{comp}, m_dat(a.size() + 1) {
        std::ranges::copy(std::make_move_iterator(a.begin()), std::make_move_iterator(a.end()), m_dat.begin() + 1);
        build();
    }

    BinaryHeap(const std::vector<T>& a, Comp comp = {}) 
        : m_comp{comp}, m_dat(a.size() + 1) {
        std::ranges::copy(a.begin(), a.end(), m_dat.begin() + 1);
        build();
    }

    const T& top() const {
        assert(size() and "HeapUnderFlow");
        return m_dat[1];
    }

    void push(T&& v) {
        m_dat.push_back(std::move(v));
        upHeap(size());
    }

    void push(const T& v) {
        m_dat.push_back(v);
        upHeap(size());
    }

    void pop() {
        assert(size() and "HeapUnderFlow");
        if (size() > 1)
            std::swap(m_dat[1], m_dat.back());
        m_dat.pop_back();
        if (size() > 1)
            downHeap(1, size());
    }

private:

    void build() {
        const usize n = size();
        for (usize i = (n >> 1) ; i ; i--) 
            downHeap(i, n);
    }

    void upHeap(usize i) {
        while (i >> 1 and m_comp(m_dat[i], m_dat[i >> 1])) {
            std::swap(m_dat[i], m_dat[i >> 1]);
            i >>= 1;
        }
    }

    void downHeap(usize i, usize n) {
        while ((i << 1) <= n) {
            usize j = i << 1;
            if (j + 1 <= n and m_comp(m_dat[j + 1], m_dat[j]))
                j++;
            if (!m_comp(m_dat[j], m_dat[i]))
                break;
            std::swap(m_dat[i], m_dat[j]);
            i = j;
        }
    }
};

} // namespace zawa
#line 6 "Src/Graph/Tree/ContourAggregation.hpp"

#line 9 "Src/Graph/Tree/ContourAggregation.hpp"
#include <numeric>
#include <tuple>
#line 13 "Src/Graph/Tree/ContourAggregation.hpp"

namespace zawa {

template <std::integral V>
class ContourAggregation {
public:

    ContourAggregation(std::vector<std::vector<V>> G) : m_lca{G}, m_cent(1), m_par(1), m_ch(1), m_offset(1) {
        const usize N = G.size();
        assert(N);
        m_inv.resize(N);
        m_pos.resize(N);
        m_ord.reserve(2 * N);
        Centroid ce{std::move(G)};
        std::vector<i32> dist(N,-1);

        auto makeNode = [&]() -> usize {
            const usize res = m_cent.size();
            m_cent.push_back(N);
            m_par.push_back(0);
            m_ch.emplace_back();
            m_offset.emplace_back();
            return res;
        };

        auto createOffset = [&](usize nd,std::vector<V> vs) {
            std::vector<usize> offset{m_ord.size()};
            if (dist[vs[0]] == 1)
                offset.push_back(m_ord.size());
            for (usize i = 0, j = 0 ; i < vs.size() ; i = j) {
                while (j < vs.size() and dist[vs[i]] == dist[vs[j]]) {
                    m_inv[vs[j]].push_back(m_ord.size());
                    m_ord.push_back(vs[j]);
                    j++;
                }
                offset.push_back(m_ord.size());
            }
            m_offset[nd] = std::move(offset);
        };

        auto compDist = [&](usize i, usize j) -> bool {
            return dist[i] < dist[j];
        };

        // {node id, height, vertices}
        auto dfs = [&](auto dfs, V v) -> std::tuple<usize,usize,std::vector<V>> {
            v = ce.rooting(v);
            std::vector<std::tuple<usize,usize,std::vector<V>>> ch;
            ce.remove(v);
            dist[v] = 0;
            for (V x : ce.adjlist(v)) {
                auto ret = dfs(dfs,x);
                for (V cur : std::get<2>(ret))
                    dist[cur] = m_lca.distance(v,cur);
                m_cent[std::get<0>(ret)] = v;
                ch.push_back(std::move(ret));
            }
            for (auto& dat : ch)
                std::ranges::sort(std::get<2>(dat),compDist);
            { // create single node of {v}
                const usize nd = m_pos[v] = makeNode();
                ch.emplace_back(nd,0u,std::vector<V>{v});
                m_cent[nd] = v;
            }
            auto comp = [&](usize i, usize j) -> bool {
                return std::get<1>(ch[i]) < std::get<1>(ch[j]);
            };
            BinaryHeap<usize,decltype(comp)> heap{[&]()->std::vector<usize>{
                std::vector<usize> res(ch.size()); 
                std::iota(res.begin(),res.end(),0u); 
                return res;
            }(),comp};
            while (std::ssize(heap) > 1) {
                const usize l = heap.top();
                heap.pop();
                const usize r = heap.top();
                heap.pop();
                const usize L = std::get<0>(ch[l]), R = std::get<0>(ch[r]);
                createOffset(L,std::get<2>(ch[l]));
                createOffset(R,std::get<2>(ch[r]));
                // merge here
                std::vector<V> vertices;
                std::ranges::merge(std::move(std::get<2>(ch[l])),std::move(std::get<2>(ch[r])),std::back_inserter(vertices),compDist);
                const usize nd = makeNode();
                m_par[L] = m_par[R] = nd;
                m_cent[L] = m_cent[R] = v;
                const usize h = std::max(std::get<1>(ch[l]),std::get<1>(ch[r]))+1;
                ch.emplace_back(nd,h,std::move(vertices));
                heap.push(ch.size()-1);
                m_ch[nd] = {L,R};
            }
            for (V x : std::get<2>(ch[heap.top()]))
                dist[x] = -1;
            return ch[heap.top()];
        };
        if (N == 1) {
            m_inv[0].push_back(0);
            m_ord.push_back(0);
        }
        else {
            std::vector<bool> vis(N);
            for (V i = 0 ; i < (V)N ; i++)
                if (!vis[i]) {
                    const auto ret = std::get<2>(dfs(dfs,i));
                    for (V v : ret)
                        vis[v] = 1;
                }
        }
    }

    inline usize size() const {
        return m_ord.size();
    }

    std::vector<usize> point(V v) const {
        assert(0 <= v and v < (V)m_inv.size());
        return m_inv[v];
    }

    std::vector<std::pair<usize,usize>> contour(V v, usize l, usize r) const {
        assert(V{0} <= v and v < (V)m_inv.size());
        std::vector<std::pair<usize,usize>> res;
        if (l >= r)
            return res;
        usize nd = m_pos[v];
        if (l == 0)
            res.push_back({m_inv[v][0],m_inv[v][0]+1});
        for ( ; m_par[nd] ; nd = m_par[nd]) {
            const usize cur = m_ch[m_par[nd]].first == nd ? m_ch[m_par[nd]].second : m_ch[m_par[nd]].first;
            const usize sub = m_lca.distance(m_cent[cur],v);
            if (sub >= r)
                continue;
            const usize L = sub >= l ? 0 : l - sub;
            const usize R = std::min(r - sub,m_offset[cur].size()-1);
            if (L >= R)
                continue;
            res.push_back({m_offset[cur][L],m_offset[cur][R]});
        }
        return res;
    }

    std::vector<std::pair<usize,usize>> contour(V v, usize d) const {
        return contour(v,d,d+1);
    }

private:

    LowestCommonAncestor<V> m_lca;

    std::vector<V> m_cent;

    std::vector<usize> m_par;

    std::vector<std::pair<usize,usize>> m_ch;

    std::vector<std::vector<usize>> m_offset;

    std::vector<V> m_ord;

    std::vector<usize> m_pos;

    std::vector<std::vector<usize>> m_inv;
    
};

} // 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"

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

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 10 "Src/DataStructure/FenwickTree/FenwickTree.hpp"
#include <type_traits>

namespace zawa {

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

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

    FenwickTree() = default;

    explicit FenwickTree(usize n) : m_n{ n }, m_bitwidth{ std::__lg(n) + 1 }, m_a(n, VM::identity()), 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) requires concepts::Inversible<Monoid> {
        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 requires concepts::Inversible<Monoid> {
        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 requires concepts::Inversible<Monoid> {
        static_assert(std::is_convertible_v<decltype(f), std::function<bool(V)>>, "maxRight's argument f must be function bool(T)");
        assert(l <= size());
        assert(f(VM::identity()));
        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 (nxt <= l or 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 requires concepts::Inversible<Monoid> {
        static_assert(std::is_convertible_v<decltype(f), std::function<bool(V)>>, "minLeft's argument f must be function bool(T)");
        assert(r <= size());
        assert(f(VM::identity()));
        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 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 6 "Test/LC/vertex_add_range_contour_sum_on_tree.test.cpp"
using namespace zawa;

#line 9 "Test/LC/vertex_add_range_contour_sum_on_tree.test.cpp"
#include <iostream>
#line 11 "Test/LC/vertex_add_range_contour_sum_on_tree.test.cpp"
using namespace std;

int main() {
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(0);
    int N, Q;
    cin >> N >> Q;
    vector<int> A(N);
    for (auto& x : A)
        cin >> x;
    vector<vector<int>> G(N);
    for (int i = 0 ; i < N - 1 ; i++) {
       int u, v;
       cin >> u >> v;
       G[u].push_back(v);
       G[v].push_back(u);
    }
    ContourAggregation sol(move(G));
    cerr << "size=" << ssize(sol) << endl;
    FenwickTree<AdditiveGroup<long long>> fen(ssize(sol));
    for (int i = 0 ; i < N ; i++) 
        for (int j : sol.point(i))
            fen.operation(j,A[i]);
    while (Q--) {
        int T;
        cin >> T;
        if (T == 0) {
            int p, x;
            cin >> p >> x;
            for (int i : sol.point(p))
                fen.operation(i,x);
        }
        else if (T == 1) {
            int p, l, r;
            cin >> p >> l >> r;
            // cout << "query " << p << ' ' << l << ' ' << r << endl;
            long long ans = 0;
            for (auto [L, R] : sol.contour(p,l,r))
                ans += fen.product(L,R);
            cout << ans << '\n';
        }
        else
            assert(0);
    }
}
Back to top page