library/tree/TreeMonoid.hpp

• View this file on GitHub
• Last update: 2025-11-24 18:49:07+09:00
• Include: #include "library/tree/TreeMonoid.hpp"

Depends on

• build/pch/stdc++.hpp
• library/algebra/Reverse.hpp
• library/algebra/monoid/Concepts.hpp
• library/segtree/SegmentTree.hpp
• library/tree/HLD.hpp

Verified with

• test/library-checker/Tree/vertex_add_path_sum.test.cpp
• test/library-checker/Tree/vertex_add_subtree_sum.test.cpp
• test/library-checker/Tree/vertex_set_path_composite.test.cpp
• test/yukicoder/650.test.cpp

Code

#pragma once
#include "library/algebra/Reverse.hpp"
#include "library/segtree/SegmentTree.hpp"
#include "library/tree/HLD.hpp"
template <typename TREE, typename Monoid> struct TreeMonoid {
    using X = typename Monoid::value_type;
    using Monoid_r = AlgebraReverse<Monoid>;
    int n;
    TREE T;
    HLD<Tree> hld;
    std::vector<int> hld_id, euler_in, euler_out;
    SegmentTree<Monoid> seg;
    SegmentTree<Monoid_r> seg_r;

    TreeMonoid(TREE T, int r = 0) : T(T), hld(T), n(T.n), seg(n), seg_r(n) {
        T.build(r);
        hld_id = hld.build(r);
    }
    TreeMonoid(TREE T, std::vector<X> a, int r = 0) : T(T), hld(T), n(T.n) {
        T.build(r);
        hld_id = hld.build(r);
        std::vector<X> hld_a(n);
        for (int v = 0; v < n; v++)
            hld_a[hld_id[v]] = a[v];
        seg = SegmentTree<Monoid>(hld_a);
        if (!Monoid::commute)
            seg_r = SegmentTree<Monoid_r>(hld_a);
    }

    void set(int v, X x) {
        seg.set(hld_id[v], x);
        if (!Monoid::commute)
            seg_r.set(hld_id[v], x);
    }
    void multiply(int v, X x) {
        seg.multiply(hld_id[v], x);
        if (!Monoid::commute)
            seg_r.multiply(hld_id[v], x);
    }
    X get(int v) { return seg.get(hld_id[v]); }

    // [u,v]パスの monoid 積
    X path_prod(int u, int v) {
        auto [path_u, path_v] = hld.path(u, v);
        X prod_u = Monoid::unit(), prod_v = Monoid::unit();
        for (const auto &[l, r] : path_u) {
            X val =
                (Monoid::commute ? seg.prod(r, l + 1) : seg_r.prod(r, l + 1));
            Monoid::Rchop(prod_u, val);
        }
        for (const auto &[l, r] : path_v) {
            X val = seg.prod(r, l + 1);
            Monoid::Lchop(val, prod_v);
        }
        return Monoid::op(prod_u, prod_v);
    }
    // root -> path
    X path_root(int v) { return path(T.root, v); }

    X subtree_prod(int v) {
        assert(Monoid::commute);
        auto [l, r] = hld.subtree(v);
        return seg.prod(l, r);
    }
};

Traceback (most recent call last):
  File "/opt/hostedtoolcache/Python/3.14.0/x64/lib/python3.14/site-packages/onlinejudge_verify/documentation/build.py", line 71, in _render_source_code_stat
    bundled_code = language.bundle(stat.path, basedir=basedir, options={'include_paths': [basedir]}).decode()
                   ~~~~~~~~~~~~~~~^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  File "/opt/hostedtoolcache/Python/3.14.0/x64/lib/python3.14/site-packages/onlinejudge_verify/languages/cplusplus.py", line 187, in bundle
    bundler.update(path)
    ~~~~~~~~~~~~~~^^^^^^
  File "/opt/hostedtoolcache/Python/3.14.0/x64/lib/python3.14/site-packages/onlinejudge_verify/languages/cplusplus_bundle.py", line 401, in update
    self.update(self._resolve(pathlib.Path(included), included_from=path))
    ~~~~~~~~~~~^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  File "/opt/hostedtoolcache/Python/3.14.0/x64/lib/python3.14/site-packages/onlinejudge_verify/languages/cplusplus_bundle.py", line 312, in update
    raise BundleErrorAt(path, i + 1, "#pragma once found in a non-first line")
onlinejudge_verify.languages.cplusplus_bundle.BundleErrorAt: library/segtree/SegmentTree.hpp: line 3: #pragma once found in a non-first line

Back to top page