Dynamic Tree Builder (for Edge) (structure/dynamic-tree/dynamic-tree-builder-for-edge.hpp)

• View this file on GitHub
• View document part on GitHub
• Last update: 2024-05-12 02:41:24+09:00
• Include: #include "structure/dynamic-tree/dynamic-tree-builder-for-edge.hpp"

Link Cut Tree や Top Tree などの動的木を簡単に構築するための Builder です。

辺に情報を乗せたい場合に使用します。動的木上では、辺も頂点とみなします。

コンストラクタ

DynamicTreeBuilderForEdge< DynamicTree, TreeDPInfo >(int n)

頂点数 n の動的木を作成します。各頂点に対し set_vertex、各辺に対し add_edge を呼び出したあとに、build を呼び出すことを期待しています。

計算量

• $O(n)$

set_vertex

void set_vertex(int u, const Info &info)

頂点 u の Info を info に設定します。

制約

• $0 \leq u \lt n$

計算量

• $O(1)$

add_edge

void add_edge(int u, int v, const Info &info, int id = -1)

頂点 u と v との間に info を持つ辺を追加します。

制約

• $0 \leq u, v \lt n$
• $u \neq v$
• $-1 \leq id \lt n$
• add_edge は $n - 1$ 回呼び出される
• 頂点 $u$ と $v$ は異なる連結成分

build

void build(int r = 0)

頂点 r を根とする動的木を構築します。

vs に各頂点へのポインタ、es に各辺へのポインタが格納されます。

計算量

• $O(n)$

Verified with

• test/verify/aoj-grl-5-a-3.test.cpp
• test/verify/yosupo-point-set-tree-path-composite-sum.test.cpp

Code

template <template <typename> typename DynamicTree, typename TreeDPInfo>
struct DynamicTreeBuilderForEdge : DynamicTree<TreeDPInfo> {
 private:
  using DT = DynamicTree<TreeDPInfo>;
  using Info = typename TreeDPInfo::Info;

  int n, e_sz;
  vector<vector<pair<int, int> > > g;

 public:
  using DT::alloc;
  using DT::link;

  vector<typename DT::NP> vs, es;

  explicit DynamicTreeBuilderForEdge(int n)
      : n(n), g(n), vs(n), es(n), e_sz(0) {}

  void set_vertex(int u, const Info &info) {
    assert(0 <= u and u < n);
    vs[u] = this->alloc(info);
  }

  void add_edge(int u, int v, const Info &info, int id = -1) {
    assert(0 <= u and u < n);
    assert(0 <= v and v < n);
    assert(u != v);
    if (id == -1) id = e_sz++;
    assert(0 <= id and id < n);
    g[u].emplace_back(v, id);
    g[v].emplace_back(u, id);
    es[id] = alloc(info);
  }

  void build(int r = 0) {
    vector<pair<int, int> > que;
    que.reserve(n);
    que.emplace_back(r, -1);
    while (not que.empty()) {
      auto [u, p] = que.back();
      que.pop_back();
      for (auto &[v, id] : g[u]) {
        if (v == p) continue;
        que.emplace_back(v, u);
        link(es[id], vs[u]);
        link(vs[v], es[id]);
      }
    }
  }
};

#line 1 "structure/dynamic-tree/dynamic-tree-builder-for-edge.hpp"
template <template <typename> typename DynamicTree, typename TreeDPInfo>
struct DynamicTreeBuilderForEdge : DynamicTree<TreeDPInfo> {
 private:
  using DT = DynamicTree<TreeDPInfo>;
  using Info = typename TreeDPInfo::Info;

  int n, e_sz;
  vector<vector<pair<int, int> > > g;

 public:
  using DT::alloc;
  using DT::link;

  vector<typename DT::NP> vs, es;

  explicit DynamicTreeBuilderForEdge(int n)
      : n(n), g(n), vs(n), es(n), e_sz(0) {}

  void set_vertex(int u, const Info &info) {
    assert(0 <= u and u < n);
    vs[u] = this->alloc(info);
  }

  void add_edge(int u, int v, const Info &info, int id = -1) {
    assert(0 <= u and u < n);
    assert(0 <= v and v < n);
    assert(u != v);
    if (id == -1) id = e_sz++;
    assert(0 <= id and id < n);
    g[u].emplace_back(v, id);
    g[v].emplace_back(u, id);
    es[id] = alloc(info);
  }

  void build(int r = 0) {
    vector<pair<int, int> > que;
    que.reserve(n);
    que.emplace_back(r, -1);
    while (not que.empty()) {
      auto [u, p] = que.back();
      que.pop_back();
      for (auto &[v, id] : g[u]) {
        if (v == p) continue;
        que.emplace_back(v, u);
        link(es[id], vs[u]);
        link(vs[v], es[id]);
      }
    }
  }
};

Back to top page