heavy-light decomposition
(include/emthrm/graph/tree/heavy-light_decomposition.hpp)

View this file on GitHub
Last update: 2023-05-12 15:57:02+09:00
Include: #include "emthrm/graph/tree/heavy-light_decomposition.hpp"

heavy edge と light edge に分類された辺を基にして、木を分解する方法である。

時間計算量

$\langle O(\lvert V \rvert), O(\log{\lvert V \rvert}) \rangle$

仕様

template <typename CostType>
struct HeavyLightDecomposition;

CostType：辺のコストを表す型

メンバ変数

名前	説明
`std::vector<int> parent`	`parent[i]` は頂点 $i$ の親の頂点番号を表す。
`std::vector<int> subtree`	`subtree[i]` は頂点 $i$ の部分木の大きさを表す。
`std::vector<int> id`	`id[i]` は頂点 $i$ の ID を表す。
`std::vector<int> inv`	`inv[i]` はID $i$ の頂点番号を表す。
`std::vector<int> head`	`head[i]` は頂点 $i$ を含む heavy path の先頭の頂点番号を表す。
`std::vector<CostType> cost`	`cost[i]` は辺 (`inv[i]`, `inv[i + 1]`) の重みを表す。

メンバ関数

名前	効果・戻り値
`explicit HeavyLightDecomposition(const std::vector<std::vector<Edge<CostType>>>& graph, const int root = 0);`	根を $\mathrm{root}$ とする木 $\mathrm{graph}$ に対してオブジェクトを構築する。
`template <typename Fn>` `void update_v(int u, int v, const Fn f) const;`	頂点 $u, v$ 間の頂点に対して $f$ を基に更新する。
`template <typename F, typename G, typename T>` `T query_v(int u, int v, const F f, const G g, const T id_t) const;`	頂点 $u, v$ 間の頂点に対する $f$ を基に $g$ でまとめたクエリの解
`template <typename Fn>` `void update_subtree_v(const int ver, const Fn f) const;`	頂点 $\mathrm{ver}$ の部分木の頂点に対して $f$ を基に更新する。
`template <typename T, typename Fn>` `T query_subtree_v(const int ver, const Fn f) const;`	頂点 $\mathrm{ver}$ の部分木の頂点に対する $f$ を基にしたクエリの解
`template <typename Fn>` `void update_e(int u, int v, const Fn f) const;`	頂点 $u, v$ 間の辺に対して $f$ を基に更新する。
`template <typename F, typename G, typename T>` `T query_e(int u, int v, const F f, const G g, const T id_t) const;`	頂点 $u, v$ 間の辺に対する $f$ を基に $g$ でまとめたクエリの解
`template <typename Fn>` `void update_subtree_e(const int ver, const Fn f) const;`	頂点 $\mathrm{ver}$ の部分木の辺に対して $f$ を基に更新する。
`template <typename T, typename Fn>` `T query_subtree_e(const int ver, const Fn f) const;`	頂点 $\mathrm{ver}$ の部分木の辺に対する $f$ を基にしたクエリの解
`int lowest_common_ancestor(int u, int v) const;`	頂点 $u, v$ の最小共通祖先

参考文献

Daniel D. Sleator and Robert Endre Tarjan: A data structure for dynamic trees, Journal of Computer and System Sciences, Vol. 26, No. 3, pp. 362–391 (1983). https://doi.org/10.1016/0022-0000(83)90006-5
https://www.slideshare.net/hcpc_hokudai/study-20150107
~~http://beet-aizu.hatenablog.com/entry/2017/12/12/235950~~
https://github.com/beet-aizu/library/blob/627950ae389af108b3c3f431f057c58891b0ba72/tree/heavylightdecomposition.cpp
https://codeforces.com/blog/entry/53170

TODO

高速化
- http://yosupo.hatenablog.com/entry/2015/10/02/233244

Submissons

https://onlinejudge.u-aizu.ac.jp/solutions/problem/2667/review/4084766/emthrm/C++14

Depends on

辺 (include/emthrm/graph/edge.hpp)

Verified with

Code

#ifndef EMTHRM_GRAPH_TREE_HEAVY_LIGHT_DECOMPOSITION_HPP_
#define EMTHRM_GRAPH_TREE_HEAVY_LIGHT_DECOMPOSITION_HPP_

#include <algorithm>
#include <utility>
#include <vector>

#include "emthrm/graph/edge.hpp"

namespace emthrm {

template <typename CostType>
struct HeavyLightDecomposition {
  std::vector<int> parent, subtree, id, inv, head;
  std::vector<CostType> cost;

  explicit HeavyLightDecomposition(
      const std::vector<std::vector<Edge<CostType>>>& graph,
      const int root = 0)
      : graph(graph) {
    const int n = graph.size();
    parent.assign(n, -1);
    subtree.assign(n, 1);
    dfs1(root);
    id.resize(n);
    inv.resize(n);
    head.assign(n, root);
    int cur_id = 0;
    dfs2(root, &cur_id);
  }

  template <typename Fn>
  void update_v(int u, int v, const Fn f) const {
    while (true) {
      if (id[u] > id[v]) std::swap(u, v);
      f(std::max(id[head[v]], id[u]), id[v] + 1);
      if (head[u] == head[v]) break;
      v = parent[head[v]];
    }
  }

  template <typename F, typename G, typename T>
  T query_v(int u, int v, const F f, const G g, const T id_t) const {
    T left = id_t, right = id_t;
    while (true) {
      if (id_t[u] > id_t[v]) {
        std::swap(u, v);
        std::swap(left, right);
      }
      left = g(left, f(std::max(id_t[head[v]], id_t[u]), id_t[v] + 1));
      if (head[u] == head[v]) break;
      v = parent[head[v]];
    }
    return g(left, right);
  }

  template <typename Fn>
  void update_subtree_v(const int ver, const Fn f) const {
    f(id[ver], id[ver] + subtree[ver]);
  }

  template <typename T, typename Fn>
  T query_subtree_v(const int ver, const Fn f) const {
    return f(id[ver], id[ver] + subtree[ver]);
  }

  template <typename Fn>
  void update_e(int u, int v, const Fn f) const {
    while (true) {
      if (id[u] > id[v]) std::swap(u, v);
      if (head[u] == head[v]) {
        f(id[u], id[v]);
        break;
      } else {
        f(id[head[v]] - 1, id[v]);
        v = parent[head[v]];
      }
    }
  }

  template <typename F, typename G, typename T>
  T query_e(int u, int v, const F f, const G g, const T id_t) const {
    T left = id_t, right = id_t;
    while (true) {
      if (id[u] > id[v]) {
        std::swap(u, v);
        std::swap(left, right);
      }
      if (head[u] == head[v]) {
        left = g(left, f(id[u], id[v]));
        break;
      } else {
        left = g(left, f(id[head[v]] - 1, id[v]));
        v = parent[head[v]];
      }
    }
    return g(left, right);
  }

  template <typename Fn>
  void update_subtree_e(const int ver, const Fn f) const {
    f(id[ver], id[ver] + subtree[ver] - 1);
  }

  template <typename T, typename Fn>
  T query_subtree_e(const int ver, const Fn f) const {
    return f(id[ver], id[ver] + subtree[ver] - 1);
  }

  int lowest_common_ancestor(int u, int v) const {
    while (true) {
      if (id[u] > id[v]) std::swap(u, v);
      if (head[u] == head[v]) break;
      v = parent[head[v]];
    }
    return u;
  }

 private:
  std::vector<std::vector<Edge<CostType>>> graph;

  void dfs1(const int ver) {
    for (int i = 0; std::cmp_less(i, graph[ver].size()); ++i) {
      Edge<CostType>& e = graph[ver][i];
      if (e.dst != parent[ver]) {
        parent[e.dst] = ver;
        dfs1(e.dst);
        subtree[ver] += subtree[e.dst];
        if (subtree[e.dst] > subtree[graph[ver].front().dst]) {
          std::swap(e, graph[ver].front());
        }
      }
    }
  }

  void dfs2(const int ver, int* cur_id) {
    id[ver] = (*cur_id)++;
    inv[id[ver]] = ver;
    for (const Edge<CostType>& e : graph[ver]) {
      if (e.dst != parent[ver]) {
        head[e.dst] = (e.dst == graph[ver].front().dst ? head[ver] : e.dst);
        cost.emplace_back(e.cost);
        dfs2(e.dst, cur_id);
      }
    }
  }
};

}  // namespace emthrm

#endif  // EMTHRM_GRAPH_TREE_HEAVY_LIGHT_DECOMPOSITION_HPP_

#line 1 "include/emthrm/graph/tree/heavy-light_decomposition.hpp"



#include <algorithm>
#include <utility>
#include <vector>

#line 1 "include/emthrm/graph/edge.hpp"
/**
 * @title 辺
 */

#ifndef EMTHRM_GRAPH_EDGE_HPP_
#define EMTHRM_GRAPH_EDGE_HPP_

#include <compare>

namespace emthrm {

template <typename CostType>
struct Edge {
  CostType cost;
  int src, dst;

  explicit Edge(const int src, const int dst, const CostType cost = 0)
      : cost(cost), src(src), dst(dst) {}

  auto operator<=>(const Edge& x) const = default;
};

}  // namespace emthrm

#endif  // EMTHRM_GRAPH_EDGE_HPP_
#line 9 "include/emthrm/graph/tree/heavy-light_decomposition.hpp"

namespace emthrm {

template <typename CostType>
struct HeavyLightDecomposition {
  std::vector<int> parent, subtree, id, inv, head;
  std::vector<CostType> cost;

  explicit HeavyLightDecomposition(
      const std::vector<std::vector<Edge<CostType>>>& graph,
      const int root = 0)
      : graph(graph) {
    const int n = graph.size();
    parent.assign(n, -1);
    subtree.assign(n, 1);
    dfs1(root);
    id.resize(n);
    inv.resize(n);
    head.assign(n, root);
    int cur_id = 0;
    dfs2(root, &cur_id);
  }

  template <typename Fn>
  void update_v(int u, int v, const Fn f) const {
    while (true) {
      if (id[u] > id[v]) std::swap(u, v);
      f(std::max(id[head[v]], id[u]), id[v] + 1);
      if (head[u] == head[v]) break;
      v = parent[head[v]];
    }
  }

  template <typename F, typename G, typename T>
  T query_v(int u, int v, const F f, const G g, const T id_t) const {
    T left = id_t, right = id_t;
    while (true) {
      if (id_t[u] > id_t[v]) {
        std::swap(u, v);
        std::swap(left, right);
      }
      left = g(left, f(std::max(id_t[head[v]], id_t[u]), id_t[v] + 1));
      if (head[u] == head[v]) break;
      v = parent[head[v]];
    }
    return g(left, right);
  }

  template <typename Fn>
  void update_subtree_v(const int ver, const Fn f) const {
    f(id[ver], id[ver] + subtree[ver]);
  }

  template <typename T, typename Fn>
  T query_subtree_v(const int ver, const Fn f) const {
    return f(id[ver], id[ver] + subtree[ver]);
  }

  template <typename Fn>
  void update_e(int u, int v, const Fn f) const {
    while (true) {
      if (id[u] > id[v]) std::swap(u, v);
      if (head[u] == head[v]) {
        f(id[u], id[v]);
        break;
      } else {
        f(id[head[v]] - 1, id[v]);
        v = parent[head[v]];
      }
    }
  }

  template <typename F, typename G, typename T>
  T query_e(int u, int v, const F f, const G g, const T id_t) const {
    T left = id_t, right = id_t;
    while (true) {
      if (id[u] > id[v]) {
        std::swap(u, v);
        std::swap(left, right);
      }
      if (head[u] == head[v]) {
        left = g(left, f(id[u], id[v]));
        break;
      } else {
        left = g(left, f(id[head[v]] - 1, id[v]));
        v = parent[head[v]];
      }
    }
    return g(left, right);
  }

  template <typename Fn>
  void update_subtree_e(const int ver, const Fn f) const {
    f(id[ver], id[ver] + subtree[ver] - 1);
  }

  template <typename T, typename Fn>
  T query_subtree_e(const int ver, const Fn f) const {
    return f(id[ver], id[ver] + subtree[ver] - 1);
  }

  int lowest_common_ancestor(int u, int v) const {
    while (true) {
      if (id[u] > id[v]) std::swap(u, v);
      if (head[u] == head[v]) break;
      v = parent[head[v]];
    }
    return u;
  }

 private:
  std::vector<std::vector<Edge<CostType>>> graph;

  void dfs1(const int ver) {
    for (int i = 0; std::cmp_less(i, graph[ver].size()); ++i) {
      Edge<CostType>& e = graph[ver][i];
      if (e.dst != parent[ver]) {
        parent[e.dst] = ver;
        dfs1(e.dst);
        subtree[ver] += subtree[e.dst];
        if (subtree[e.dst] > subtree[graph[ver].front().dst]) {
          std::swap(e, graph[ver].front());
        }
      }
    }
  }

  void dfs2(const int ver, int* cur_id) {
    id[ver] = (*cur_id)++;
    inv[id[ver]] = ver;
    for (const Edge<CostType>& e : graph[ver]) {
      if (e.dst != parent[ver]) {
        head[e.dst] = (e.dst == graph[ver].front().dst ? head[ver] : e.dst);
        cost.emplace_back(e.cost);
        dfs2(e.dst, cur_id);
      }
    }
  }
};

}  // namespace emthrm

heavy-light decomposition (include/emthrm/graph/tree/heavy-light_decomposition.hpp)

時間計算量

仕様

メンバ変数

メンバ関数

参考文献

TODO

Submissons

Depends on

Verified with

Code

heavy-light decomposition
(include/emthrm/graph/tree/heavy-light_decomposition.hpp)