Dynamic Tree Builder (for Vertex) (structure/dynamic-tree/dynamic-tree-builder-for-vertex.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-vertex.hpp"

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

コンストラクタ

DynamicTreeBuilderForVertex< 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)

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

制約

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

build

void build(int r = 0)

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

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

計算量

• $O(n)$

Verified with

• test/verify/aoj-2450-5.test.cpp
• test/verify/yosupo-dynamic-tree-subtree-add-subtree-sum-2.test.cpp
• test/verify/yosupo-dynamic-tree-vertex-add-path-sum-4.test.cpp
• test/verify/yosupo-dynamic-tree-vertex-add-subtree-sum-3.test.cpp
• test/verify/yosupo-dynamic-tree-vertex-set-path-composite-4.test.cpp

Code

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

  int n;
  vector<vector<int> > g;

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

  vector<typename DT::NP> vs;

  explicit DynamicTreeBuilderForVertex(int n) : n(n), g(n), vs(n) {}

  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) {
    assert(0 <= u and u < n);
    assert(0 <= v and v < n);
    assert(u != v);
    g[u].emplace_back(v);
    g[v].emplace_back(u);
  }

  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 : g[u]) {
        if (v == p) continue;
        que.emplace_back(v, u);
        link(vs[v], vs[u]);
      }
    }
  }
};

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

  int n;
  vector<vector<int> > g;

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

  vector<typename DT::NP> vs;

  explicit DynamicTreeBuilderForVertex(int n) : n(n), g(n), vs(n) {}

  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) {
    assert(0 <= u and u < n);
    assert(0 <= v and v < n);
    assert(u != v);
    g[u].emplace_back(v);
    g[v].emplace_back(u);
  }

  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 : g[u]) {
        if (v == p) continue;
        que.emplace_back(v, u);
        link(vs[v], vs[u]);
      }
    }
  }
};

Back to top page