Static Tree Path Product
(tree/static-tree-path-prod.hpp)

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

静的な木のパス上のモノイド積を求める．

StaticTreePathProd<M, vertex, edge> として使う．M はモノイド，vertex と edge はそれぞれ頂点と辺の値を積へ含めるかを表し，少なくとも一方を true とする．辺の値を使う場合，辺は weight を持つものとする．積の順序はパスを始点から終点へ進む順である．

可換モノイドでは StaticTreePathProdCommutative<M, vertex, edge> を使うことで，使用するメモリと定数倍を減らせる．

• StaticTreePathProd(g, vertex_value, root)：頂点の値を使う場合に，木 g と頂点列 vertex_value から構築する．
• StaticTreePathProd(g, root)：辺の値だけを使う場合に，木 g から構築する．
• lca(x, y)：根を root とした頂点 $x,y$ の最小共通祖先を返す．
• prod(x, y)：頂点 $x$ から $y$ までのパス上の積を返す．

構築は $O(N\log N)$ 時間，$O(N\log N)$ 空間．lca と prod は $O(\log N)$ 時間．

Depends on

• algebraic-structure/magma.hpp
• algebraic-structure/monoid.hpp
• algebraic-structure/util.hpp

Verified with

• verify/tree/UNIT_static_tree_path_prod.test.cpp

Code

#pragma once

#include "algebraic-structure/monoid.hpp"

template <class M, bool vertex, bool edge>
REQUIRES(Monoid<M>)
struct StaticTreePathProd {
  static_assert(vertex || edge);
  using T = M::value_type;

  StaticTreePathProd() {}
  template <class G>
  StaticTreePathProd(const G& g, const vector<T>& vertex_value, int root = 0)
      : n(g.size()), data(vertex_value) {
    static_assert(vertex);
    assert((int)data.size() == n);
    build(g, root);
  }
  template <class G>
  StaticTreePathProd(const G& g, int root = 0) : n(g.size()) {
    static_assert(edge && !vertex);
    build(g, root);
  }

  int lca(int x, int y) const {
    assert(0 <= x && x < n && 0 <= y && y < n);
    if (depth[x] < depth[y]) swap(x, y);
    x = climb(x, depth[x] - depth[y]);
    if (x == y) return x;
    for (int k = log - 1; k >= 0; k--) {
      if (parent[k][x] != parent[k][y]) x = parent[k][x], y = parent[k][y];
    }
    return parent[0][x];
  }
  T prod(int x, int y) const {
    assert(0 <= x && x < n && 0 <= y && y < n);
    int z = lca(x, y);
    T pl = M::e(), pr = M::e();
    for (int d = depth[x] - depth[z]; d > 0;) {
      int k = topbit(d);
      pl = M::op(pl, prod_up[k][x]);
      x = parent[k][x];
      d -= 1 << k;
    }
    for (int d = depth[y] - depth[z]; d > 0;) {
      int k = topbit(d);
      pr = M::op(prod_down[k][y], pr);
      y = parent[k][y];
      d -= 1 << k;
    }
    if constexpr (vertex) pl = M::op(pl, data[z]);
    return M::op(pl, pr);
  }

 private:
  int n = 0, log = 0;
  vector<T> data;
  vector<int> depth;
  vector<vector<int>> parent;
  vector<vector<T>> prod_up, prod_down;

  int climb(int x, int d) const {
    for (int k = 0; d > 0; k++, d >>= 1)
      if (d & 1) x = parent[k][x];
    return x;
  }
  template <class G>
  void build(const G& g, int root) {
    assert(n > 0);
    assert(0 <= root && root < n);
    log = 1;
    while ((1 << log) <= n) log++;
    depth.assign(n, 0);
    parent.assign(log, vector<int>(n, root));
    prod_up.assign(log, vector<T>(n, M::e()));
    prod_down.assign(log, vector<T>(n, M::e()));
    vector<int> order = {root};
    for (int i = 0; i < (int)order.size(); i++) {
      int x = order[i];
      for (const auto& e : g[x]) {
        int y = e.to;
        if (y == parent[0][x]) continue;
        parent[0][y] = x;
        depth[y] = depth[x] + 1;
        if constexpr (edge) {
          prod_up[0][y] = vertex ? M::op(data[y], e.weight) : e.weight;
          prod_down[0][y] = vertex ? M::op(e.weight, data[y]) : e.weight;
        } else {
          prod_up[0][y] = prod_down[0][y] = data[y];
        }
        order.push_back(y);
      }
    }
    assert((int)order.size() == n);
    for (int k = 0; k + 1 < log; k++) {
      for (int x = 0; x < n; x++) {
        int p = parent[k][x];
        parent[k + 1][x] = parent[k][p];
        prod_up[k + 1][x] = M::op(prod_up[k][x], prod_up[k][p]);
        prod_down[k + 1][x] = M::op(prod_down[k][p], prod_down[k][x]);
      }
    }
  }
};

template <class M, bool vertex, bool edge>
REQUIRES(Monoid<M>)
struct StaticTreePathProdCommutative {
  static_assert(vertex || edge);
  using T = M::value_type;

  StaticTreePathProdCommutative() {}
  template <class G>
  StaticTreePathProdCommutative(const G& g, const vector<T>& vertex_value, int root = 0)
      : n(g.size()), data(vertex_value) {
    static_assert(vertex);
    assert((int)data.size() == n);
    build(g, root);
  }
  template <class G>
  StaticTreePathProdCommutative(const G& g, int root = 0) : n(g.size()) {
    static_assert(edge && !vertex);
    build(g, root);
  }

  int lca(int x, int y) const {
    assert(0 <= x && x < n && 0 <= y && y < n);
    if (depth[x] < depth[y]) swap(x, y);
    x = climb(x, depth[x] - depth[y]);
    if (x == y) return x;
    for (int k = log - 1; k >= 0; k--) {
      if (parent[k][x] != parent[k][y]) x = parent[k][x], y = parent[k][y];
    }
    return parent[0][x];
  }
  T prod(int x, int y) const {
    assert(0 <= x && x < n && 0 <= y && y < n);
    int z = lca(x, y);
    T p = M::e();
    for (int d = depth[x] - depth[z]; d > 0;) {
      int k = topbit(d);
      p = M::op(p, prod_db[k][x]);
      x = parent[k][x];
      d -= 1 << k;
    }
    for (int d = depth[y] - depth[z]; d > 0;) {
      int k = topbit(d);
      p = M::op(p, prod_db[k][y]);
      y = parent[k][y];
      d -= 1 << k;
    }
    if constexpr (vertex) p = M::op(p, data[z]);
    return p;
  }

 private:
  int n = 0, log = 0;
  vector<T> data;
  vector<int> depth;
  vector<vector<int>> parent;
  vector<vector<T>> prod_db;

  int climb(int x, int d) const {
    for (int k = 0; d > 0; k++, d >>= 1)
      if (d & 1) x = parent[k][x];
    return x;
  }
  template <class G>
  void build(const G& g, int root) {
    assert(n > 0);
    assert(0 <= root && root < n);
    log = 1;
    while ((1 << log) <= n) log++;
    depth.assign(n, 0);
    parent.assign(log, vector<int>(n, root));
    prod_db.assign(log, vector<T>(n, M::e()));
    vector<int> order = {root};
    for (int i = 0; i < (int)order.size(); i++) {
      int x = order[i];
      for (const auto& e : g[x]) {
        int y = e.to;
        if (y == parent[0][x]) continue;
        parent[0][y] = x;
        depth[y] = depth[x] + 1;
        if constexpr (edge)
          prod_db[0][y] = vertex ? M::op(data[y], e.weight) : e.weight;
        else
          prod_db[0][y] = data[y];
        order.push_back(y);
      }
    }
    assert((int)order.size() == n);
    for (int k = 0; k + 1 < log; k++) {
      for (int x = 0; x < n; x++) {
        int p = parent[k][x];
        parent[k + 1][x] = parent[k][p];
        prod_db[k + 1][x] = M::op(prod_db[k][x], prod_db[k][p]);
      }
    }
  }
};

/**
 * @brief Static Tree Path Product
 * @docs docs/tree/static-tree-path-prod.md
 */

#line 2 "tree/static-tree-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 4 "tree/static-tree-path-prod.hpp"

template <class M, bool vertex, bool edge>
REQUIRES(Monoid<M>)
struct StaticTreePathProd {
  static_assert(vertex || edge);
  using T = M::value_type;

  StaticTreePathProd() {}
  template <class G>
  StaticTreePathProd(const G& g, const vector<T>& vertex_value, int root = 0)
      : n(g.size()), data(vertex_value) {
    static_assert(vertex);
    assert((int)data.size() == n);
    build(g, root);
  }
  template <class G>
  StaticTreePathProd(const G& g, int root = 0) : n(g.size()) {
    static_assert(edge && !vertex);
    build(g, root);
  }

  int lca(int x, int y) const {
    assert(0 <= x && x < n && 0 <= y && y < n);
    if (depth[x] < depth[y]) swap(x, y);
    x = climb(x, depth[x] - depth[y]);
    if (x == y) return x;
    for (int k = log - 1; k >= 0; k--) {
      if (parent[k][x] != parent[k][y]) x = parent[k][x], y = parent[k][y];
    }
    return parent[0][x];
  }
  T prod(int x, int y) const {
    assert(0 <= x && x < n && 0 <= y && y < n);
    int z = lca(x, y);
    T pl = M::e(), pr = M::e();
    for (int d = depth[x] - depth[z]; d > 0;) {
      int k = topbit(d);
      pl = M::op(pl, prod_up[k][x]);
      x = parent[k][x];
      d -= 1 << k;
    }
    for (int d = depth[y] - depth[z]; d > 0;) {
      int k = topbit(d);
      pr = M::op(prod_down[k][y], pr);
      y = parent[k][y];
      d -= 1 << k;
    }
    if constexpr (vertex) pl = M::op(pl, data[z]);
    return M::op(pl, pr);
  }

 private:
  int n = 0, log = 0;
  vector<T> data;
  vector<int> depth;
  vector<vector<int>> parent;
  vector<vector<T>> prod_up, prod_down;

  int climb(int x, int d) const {
    for (int k = 0; d > 0; k++, d >>= 1)
      if (d & 1) x = parent[k][x];
    return x;
  }
  template <class G>
  void build(const G& g, int root) {
    assert(n > 0);
    assert(0 <= root && root < n);
    log = 1;
    while ((1 << log) <= n) log++;
    depth.assign(n, 0);
    parent.assign(log, vector<int>(n, root));
    prod_up.assign(log, vector<T>(n, M::e()));
    prod_down.assign(log, vector<T>(n, M::e()));
    vector<int> order = {root};
    for (int i = 0; i < (int)order.size(); i++) {
      int x = order[i];
      for (const auto& e : g[x]) {
        int y = e.to;
        if (y == parent[0][x]) continue;
        parent[0][y] = x;
        depth[y] = depth[x] + 1;
        if constexpr (edge) {
          prod_up[0][y] = vertex ? M::op(data[y], e.weight) : e.weight;
          prod_down[0][y] = vertex ? M::op(e.weight, data[y]) : e.weight;
        } else {
          prod_up[0][y] = prod_down[0][y] = data[y];
        }
        order.push_back(y);
      }
    }
    assert((int)order.size() == n);
    for (int k = 0; k + 1 < log; k++) {
      for (int x = 0; x < n; x++) {
        int p = parent[k][x];
        parent[k + 1][x] = parent[k][p];
        prod_up[k + 1][x] = M::op(prod_up[k][x], prod_up[k][p]);
        prod_down[k + 1][x] = M::op(prod_down[k][p], prod_down[k][x]);
      }
    }
  }
};

template <class M, bool vertex, bool edge>
REQUIRES(Monoid<M>)
struct StaticTreePathProdCommutative {
  static_assert(vertex || edge);
  using T = M::value_type;

  StaticTreePathProdCommutative() {}
  template <class G>
  StaticTreePathProdCommutative(const G& g, const vector<T>& vertex_value, int root = 0)
      : n(g.size()), data(vertex_value) {
    static_assert(vertex);
    assert((int)data.size() == n);
    build(g, root);
  }
  template <class G>
  StaticTreePathProdCommutative(const G& g, int root = 0) : n(g.size()) {
    static_assert(edge && !vertex);
    build(g, root);
  }

  int lca(int x, int y) const {
    assert(0 <= x && x < n && 0 <= y && y < n);
    if (depth[x] < depth[y]) swap(x, y);
    x = climb(x, depth[x] - depth[y]);
    if (x == y) return x;
    for (int k = log - 1; k >= 0; k--) {
      if (parent[k][x] != parent[k][y]) x = parent[k][x], y = parent[k][y];
    }
    return parent[0][x];
  }
  T prod(int x, int y) const {
    assert(0 <= x && x < n && 0 <= y && y < n);
    int z = lca(x, y);
    T p = M::e();
    for (int d = depth[x] - depth[z]; d > 0;) {
      int k = topbit(d);
      p = M::op(p, prod_db[k][x]);
      x = parent[k][x];
      d -= 1 << k;
    }
    for (int d = depth[y] - depth[z]; d > 0;) {
      int k = topbit(d);
      p = M::op(p, prod_db[k][y]);
      y = parent[k][y];
      d -= 1 << k;
    }
    if constexpr (vertex) p = M::op(p, data[z]);
    return p;
  }

 private:
  int n = 0, log = 0;
  vector<T> data;
  vector<int> depth;
  vector<vector<int>> parent;
  vector<vector<T>> prod_db;

  int climb(int x, int d) const {
    for (int k = 0; d > 0; k++, d >>= 1)
      if (d & 1) x = parent[k][x];
    return x;
  }
  template <class G>
  void build(const G& g, int root) {
    assert(n > 0);
    assert(0 <= root && root < n);
    log = 1;
    while ((1 << log) <= n) log++;
    depth.assign(n, 0);
    parent.assign(log, vector<int>(n, root));
    prod_db.assign(log, vector<T>(n, M::e()));
    vector<int> order = {root};
    for (int i = 0; i < (int)order.size(); i++) {
      int x = order[i];
      for (const auto& e : g[x]) {
        int y = e.to;
        if (y == parent[0][x]) continue;
        parent[0][y] = x;
        depth[y] = depth[x] + 1;
        if constexpr (edge)
          prod_db[0][y] = vertex ? M::op(data[y], e.weight) : e.weight;
        else
          prod_db[0][y] = data[y];
        order.push_back(y);
      }
    }
    assert((int)order.size() == n);
    for (int k = 0; k + 1 < log; k++) {
      for (int x = 0; x < n; x++) {
        int p = parent[k][x];
        parent[k + 1][x] = parent[k][p];
        prod_db[k + 1][x] = M::op(prod_db[k][x], prod_db[k][p]);
      }
    }
  }
};

/**
 * @brief Static Tree Path Product
 * @docs docs/tree/static-tree-path-prod.md
 */

Back to top page