Tree Vertex Set Path Product
(tree/tree-vertex-set-path-prod.hpp)

• View this file on GitHub
• Last update: 2026-09-05 04:46:11+09:00
• Include: #include "tree/tree-vertex-set-path-prod.hpp"

木の頂点の値を更新し，パス上のモノイド積を求める．

TreeVertexSetPathProd<M> として使う．M はモノイドであり，その演算を $\circ$ とする．積の順序はパスを始点から終点へ進む順である．可換モノイドでは TreeVertexSetPathProdCommutative<M> を使うことで，使用するメモリと定数倍を減らせる．

• TreeVertexSetPathProd(g, vertex_value, root)：木 g と頂点列 vertex_value から構築する．
• set(x, v)：頂点 $x$ の値を $v$ に変更する．
• apply(x, v)：頂点 $x$ の値を $A_x\gets A_x\circ v$ に変更する．
• prod(x, y)：頂点 $x$ から $y$ までのパス上の積を返す．両端点を含む．

構築は $O(N)$ 時間，$O(N)$ 空間．set と apply は $O(\log N)$ 時間，prod は $O(\log^2 N)$ 時間．

資料

• Library Checker: Vertex Set Path Composite
• Library Checker: Vertex Add Path Sum

Depends on

• algebraic-structure/magma.hpp
• algebraic-structure/monoid.hpp
• algebraic-structure/util.hpp
• Segment Tree (segment-tree/segment-tree.hpp)
• Heavy Light Decomposition (tree/heavy-light-decomposition.hpp)

Verified with

• verify/tree/LC_vertex_add_path_sum.test.cpp
• verify/tree/LC_vertex_set_path_composite.test.cpp

Code

#pragma once

#include "algebraic-structure/monoid.hpp"
#include "tree/heavy-light-decomposition.hpp"
#include "segment-tree/segment-tree.hpp"

template <class M>
REQUIRES(Monoid<M>)
struct TreeVertexSetPathProd {
  using T = M::value_type;
  TreeVertexSetPathProd() {}
  template <class G>
  TreeVertexSetPathProd(const G& g, const vector<T>& vertex_value, int root = 0) : n(g.size()), hld(g, root) {
    assert((int)vertex_value.size() == n);
    vector<T> data(g.size());
    for (int i = 0; i < n; i++) data[i] = vertex_value[hld.vertices[i]];
    seg = SegmentTree<M>(data);
    reverse(data.begin(), data.end());
    segr = SegmentTree<M>(data);
  }
  void set(int x, T v) {
    seg.set(hld.pos[x], v);
    segr.set(n - 1 - hld.pos[x], v);
  }
  void apply(int x, T v) {
    seg.apply(hld.pos[x], v);
    segr.apply(n - 1 - hld.pos[x], v);
  }
  T prod(int x, int y) {
    T p = M::e();
    hld.path(x, y, [&](int l, int r, bool rev) {
      p = M::op(p, rev ? segr.prod(n - r, n - l) : seg.prod(l, r));
    });
    return p;
  }

 private:
  int n;
  HeavyLightDecomposition hld;
  SegmentTree<M> seg, segr;
};

template <class M>
REQUIRES(Monoid<M>)
struct TreeVertexSetPathProdCommutative {
  using T = M::value_type;
  TreeVertexSetPathProdCommutative() {}
  template <class G>
  TreeVertexSetPathProdCommutative(const G& g, const vector<T>& vertex_value, int root = 0)
      : n(g.size()), hld(g, root) {
    assert((int)vertex_value.size() == n);
    vector<T> data(g.size());
    for (int i = 0; i < n; i++) data[i] = vertex_value[hld.vertices[i]];
    seg = SegmentTree<M>(data);
  }
  void set(int x, T v) { seg.set(hld.pos[x], v); }
  void apply(int x, T v) { seg.apply(hld.pos[x], v); }
  T prod(int x, int y) {
    T p = M::e();
    hld.path(x, y, [&](int l, int r, bool) { p = M::op(p, seg.prod(l, r)); });
    return p;
  }

 private:
  int n;
  HeavyLightDecomposition hld;
  SegmentTree<M> seg;
};

/**
 * @brief Tree Vertex Set Path Product
 * @docs docs/tree/tree-vertex-set-path-prod.md
 */

#line 2 "tree/tree-vertex-set-path-prod.hpp"

#line 2 "algebraic-structure/util.hpp"
#ifdef __cpp_concepts
#define REQUIRES(...) requires __VA_ARGS__
#else
#define REQUIRES(...)
#endif
#line 3 "algebraic-structure/magma.hpp"

#ifdef __cpp_concepts
template <class M>
concept Magma = requires(typename M::value_type x, typename M::value_type y) {
  typename M::value_type;
  { M::op(x, y) } -> same_as<typename M::value_type>;
};
#endif

template <class T>
struct AddMagma {
  using value_type = T;
  static T op(T x, T y) { return x + y; }
};
template <class T>
struct MulMagma {
  using value_type = T;
  static T op(T x, T y) { return x * y; }
};
template <class T, T id>
struct MaxMagma {
  using value_type = T;
  static T op(T x, T y) { return x > y ? x : y; }
};
template <class T, T id>
struct MinMagma {
  using value_type = T;
  static T op(T x, T y) { return x < y ? x : y; }
};
#line 3 "algebraic-structure/monoid.hpp"

#ifdef __cpp_concepts
template <class M>
concept Monoid = Magma<M> && requires {
  { M::e() } -> same_as<typename M::value_type>;
};
#endif

template <class T>
struct AddMonoid {
  using value_type = T;
  static T op(T x, T y) { return x + y; }
  static T e() { return T(0); }
};
template <class T>
struct MulMonoid {
  using value_type = T;
  static T op(T x, T y) { return x * y; }
  static T e() { return T(1); }
};
template <class T, T id>
struct MaxMonoid {
  using value_type = T;
  static T op(T x, T y) { return x > y ? x : y; }
  static T e() { return id; }
};
template <class T, T id>
struct MinMonoid {
  using value_type = T;
  static T op(T x, T y) { return x < y ? x : y; }
  static T e() { return id; }
};
#line 2 "tree/heavy-light-decomposition.hpp"

struct HeavyLightDecomposition {
  vector<int> vertices, pos, parent, depth, heavy_root;
  HeavyLightDecomposition() {}
  template <class G>
  HeavyLightDecomposition(const G& g, int root = 0) { build(g, root); }

  template <class F>
  void path(int x, int y, F f) const {
    int n = parent.size();
    assert(0 <= x && x < n);
    assert(0 <= y && y < n);
    array<pair<int, int>, numeric_limits<unsigned int>::digits> right;
    int right_size = 0;
    while (heavy_root[x] != heavy_root[y]) {
      int hx = heavy_root[x], hy = heavy_root[y];
      if (depth[hx] >= depth[hy]) {
        f(pos[hx], pos[x] + 1, true);
        x = parent[hx];
      } else {
        assert(right_size < static_cast<int>(right.size()));
        right[right_size++] = {pos[hy], pos[y] + 1};
        y = parent[hy];
      }
    }
    if (pos[x] <= pos[y])
      f(pos[x], pos[y] + 1, false);
    else
      f(pos[y], pos[x] + 1, true);
    for (int i = right_size - 1; i >= 0; i--) f(right[i].first, right[i].second, false);
  }

  template <class G>
  void build(const G& g, int root = 0) {
    int n = g.size();
    assert(n > 0);
    assert(0 <= root && root < n);
    parent.assign(n, -2);
    depth.assign(n, 0);
    parent[root] = -1;
    vertices.clear();
    vertices.reserve(n);
    stack<int> st;
    st.push(root);
    while (!st.empty()) {
      int x = st.top();
      st.pop();
      vertices.push_back(x);
      for (const auto& e : g[x]) {
        int y = e.to;
        if (parent[y] != -2) continue;
        parent[y] = x;
        depth[y] = depth[x] + 1;
        st.push(y);
      }
    }
    assert(static_cast<int>(vertices.size()) == n);
    vector<int> subtree_size(n, 1), heavy(n, -1);
    for (auto it = vertices.rbegin(); it != vertices.rend(); it++) {
      int x = *it, p = parent[x];
      if (p != -1) {
        subtree_size[p] += subtree_size[x];
        if (heavy[p] == -1 || subtree_size[x] > subtree_size[heavy[p]]) heavy[p] = x;
      }
    }
    vertices.clear();
    pos.resize(n);
    heavy_root.resize(n);
    stack<pair<int, int>> paths;
    paths.push({root, root});
    while (!paths.empty()) {
      auto [start, head] = paths.top();
      paths.pop();
      for (int x = start; x != -1; x = heavy[x]) {
        pos[x] = static_cast<int>(vertices.size());
        vertices.push_back(x);
        heavy_root[x] = head;
        for (const auto& e : g[x]) {
          int y = e.to;
          if (parent[y] == x && y != heavy[x]) paths.push({y, y});
        }
      }
    }
  }
};

/**
 * @brief Heavy Light Decomposition
 * @docs docs/tree/heavy-light-decomposition.md
 */
#line 3 "segment-tree/segment-tree.hpp"

template <class M>
REQUIRES(Monoid<M>)
struct SegmentTree {
  using T = typename M::value_type;

 private:
  int _n, size, log;
  vector<T> d;
  void update(int p) { d[p] = M::op(d[2 * p], d[2 * p + 1]); }

 public:
  SegmentTree() : SegmentTree(0) {}
  explicit SegmentTree(int sz) : SegmentTree(vector<T>(sz, M::e())) {}
  explicit SegmentTree(const vector<T>& v) : _n(v.size()) {
    size = 1, log = 0;
    while (size < _n) size <<= 1, log++;
    d.assign(2 * size, M::e());
    for (int i = 0; i < _n; i++) d[size + i] = v[i];
    for (int i = size - 1; i > 0; i--) update(i);
  }
  void clear() { fill(d.begin(), d.end(), M::e()); }

  void set_without_update(int p, T v) { d[p + size] = v; }
  void all_update() {
    for (int i = size - 1; i > 0; i--) update(i);
  }
  T get(int p) {
    assert(0 <= p && p <= _n);
    return d[p + size];
  }
  void set(int p, T v) {
    assert(0 <= p && p <= _n);
    p += size;
    d[p] = v;
    for (int i = 1; i <= log; i++) update(p >> i);
  }
  void apply(int p, T v) {
    assert(0 <= p && p <= _n);
    p += size;
    d[p] = M::op(d[p], v);
    for (int i = 1; i <= log; i++) update(p >> i);
  }
  T all_prod() { return d[1]; }
  T prod(int l, int r) {
    if (l >= r) return M::e();
    assert(0 <= l && l <= r && r <= _n);
    T sl = M::e(), sr = M::e();
    l += size, r += size;
    while (l < r) {
      if ((l & 1) != 0) sl = M::op(sl, d[l++]);
      if ((r & 1) != 0) sr = M::op(d[--r], sr);
      l >>= 1, r >>= 1;
    }
    return M::op(sl, sr);
  }

  template <bool (*f)(T)>
  int max_right(int l) const {
    return max_right(l, [](T x) { return f(x); });
  }
  template <class F>
  int max_right(int l, F f) const {
    assert(0 <= l && l <= size);
    assert(f(M::e()));
    if (l == _n) return _n;
    l += size;
    T s = M::e();
    do {
      while (l % 2 == 0) l >>= 1;
      if (!f(M::op(s, d[l]))) {
        while (l < size) {
          l <<= 1;
          if (f(M::op(s, d[l]))) s = M::op(s, d[l++]);
        }
        return l - size;
      }
      s = M::op(s, d[l++]);
    } while ((l & -l) != l);
    return _n;
  }

  template <bool (*f)(T)>
  int min_left(int r) const {
    return min_left(r, [](T x) { return f(x); });
  }
  template <class F>
  int min_left(int r, F f) const {
    assert(0 <= r && r <= _n);
    assert(f(M::e()));
    if (r == 0) return 0;
    r += size;
    T s = M::e();
    do {
      r--;
      while (r > 1 && (r % 2)) r >>= 1;
      if (!f(M::op(d[r], s))) {
        while (r < size) {
          r <<= 1, r++;
          if (f(M::op(d[r], s))) s = M::op(d[r--], s);
        }
        return r + 1 - size;
      }
      s = M::op(d[r], s);
    } while ((r & -r) != r);
    return 0;
  }
};

/**
 * @brief Segment Tree
 * @docs docs/segment-tree/segment-tree.md
 */
#line 6 "tree/tree-vertex-set-path-prod.hpp"

template <class M>
REQUIRES(Monoid<M>)
struct TreeVertexSetPathProd {
  using T = M::value_type;
  TreeVertexSetPathProd() {}
  template <class G>
  TreeVertexSetPathProd(const G& g, const vector<T>& vertex_value, int root = 0) : n(g.size()), hld(g, root) {
    assert((int)vertex_value.size() == n);
    vector<T> data(g.size());
    for (int i = 0; i < n; i++) data[i] = vertex_value[hld.vertices[i]];
    seg = SegmentTree<M>(data);
    reverse(data.begin(), data.end());
    segr = SegmentTree<M>(data);
  }
  void set(int x, T v) {
    seg.set(hld.pos[x], v);
    segr.set(n - 1 - hld.pos[x], v);
  }
  void apply(int x, T v) {
    seg.apply(hld.pos[x], v);
    segr.apply(n - 1 - hld.pos[x], v);
  }
  T prod(int x, int y) {
    T p = M::e();
    hld.path(x, y, [&](int l, int r, bool rev) {
      p = M::op(p, rev ? segr.prod(n - r, n - l) : seg.prod(l, r));
    });
    return p;
  }

 private:
  int n;
  HeavyLightDecomposition hld;
  SegmentTree<M> seg, segr;
};

template <class M>
REQUIRES(Monoid<M>)
struct TreeVertexSetPathProdCommutative {
  using T = M::value_type;
  TreeVertexSetPathProdCommutative() {}
  template <class G>
  TreeVertexSetPathProdCommutative(const G& g, const vector<T>& vertex_value, int root = 0)
      : n(g.size()), hld(g, root) {
    assert((int)vertex_value.size() == n);
    vector<T> data(g.size());
    for (int i = 0; i < n; i++) data[i] = vertex_value[hld.vertices[i]];
    seg = SegmentTree<M>(data);
  }
  void set(int x, T v) { seg.set(hld.pos[x], v); }
  void apply(int x, T v) { seg.apply(hld.pos[x], v); }
  T prod(int x, int y) {
    T p = M::e();
    hld.path(x, y, [&](int l, int r, bool) { p = M::op(p, seg.prod(l, r)); });
    return p;
  }

 private:
  int n;
  HeavyLightDecomposition hld;
  SegmentTree<M> seg;
};

/**
 * @brief Tree Vertex Set Path Product
 * @docs docs/tree/tree-vertex-set-path-prod.md
 */

Back to top page