重軽分解 ( HL 分解)
(GraphTheory/HeavyLightDecomposition.hpp)

View this file on GitHub
Last update: 2021-03-12 18:03:59+09:00
Include: #include "GraphTheory/HeavyLightDecomposition.hpp"
Link: https://tkmst201.github.io/Library/GraphTheory/HeavyLightDecomposition.hpp

概要

森に含まれる各木に対して重軽分解とオイラーツアーを行います。おまけで任意の $2$ 頂点の LCA を空間 $\Theta(N\log{\log{N}})$ クエリ $\mathcal{O}(\log{\log{N}})$ で求めることもできます。
重軽分解についてはページ下部にある参考リンク先を参照してください。

HeavyLightDecomposition(const Graph & g, bool LCA = false)
- LCA $= false$ : $\Theta(N)$, LCA $= true$ : $\mathcal{O}(N \log{\log{N}})$ g の各木に対して重軽分解とオイラーツアーを行う
HeavyLightDecomposition(const Graph & g, int root, bool LCA = false)
- LCA $= false$ : $\Theta(N)$, LCA $= true$ : $\mathcal{O}(N \log{\log{N}})$ 頂点 root を根とした根付き木 g に対して重軽分解とオイラーツアーを行う
int size()
- $\Theta(1)$ グラフの頂点数 $N$ を返す
int par(int v)
- $\Theta(1)$ 頂点 $v$ の親を返す
int tree_id(int v)
- $\Theta(1)$ 頂点 $v$ が属する木の ID を返す
int tree_cnt()
- $\Theta(1)$ グラフ g に含まれる木の個数を返す
int trees()
- $\Theta(1)$ グラフ g に含まれる木の根を ID の昇順に返す
int heavy(int v)
- $\Theta(1)$ 頂点 v が属する heavy-edge の ID を返す
int head(int k)
- $\Theta(1)$ heavy-edge k に含まれる頂点の内、最も根側の頂点番号を返す
int heavy_size()
- $\Theta(1)$ heavy-edge の本数を返す
int heavy_size(int k)
- $\Theta(1)$ heavy-edge k に含まれるの頂点数を返す
int heavy_depth(int k)
- $\Theta(1)$ heavy-edge k から根が属する heavy-edge 間のパス上に含まれる heavy-edge の個数 $-1$ を返す
int in(int v)
- $\Theta(1)$ 頂点 v に入ったときの時刻を返す
int out(int v)
- $\Theta(1)$ 頂点 v から出たときの時刻を返す
const std::vector<std::vector<int>> & par_dblng()
- $\Theta(1)$ $[i][j] :=$ heavy-edge $j$ から $2^i$ 回根方向に heavy-edge を登ったすぐの頂点番号(存在しなければ根の番号)
std::pair<int, int> lca_heavy(int x, int y)
- $\mathcal{O}(\log{\log{N}})$ 頂点 $x, y$ から根側に移動して同じ heavy-edge 内となるような最も移動回数の和が小さい頂点位置の組を返す
lca(int x, int y)
- $\mathcal{O}(\log{\log{N}})$ 頂点 $x, y$ の最近共通祖先を返す

コンストラクタ

以下、グラフの頂点数を $N$ とします。

HeavyLightDecomposition(const Graph & g, bool LCA = false)

根を指定せずに g の各木に対して重軽分解とオイラーツアーを行います。根はその木に含まれる最小の番号の頂点となります。 LCA を求めたい場合は、LCA $= true$ を指定してください。

制約

g は森

計算量

LCA $= false$ : $\Theta(N)$
LCA $= true$ : $\mathcal{O}(N \log{\log{N}})$

HeavyLightDecomposition(const Graph & g, int root, bool LCA = false)

頂点 root を根とした根付き木 g に対して重軽分解とオイラーツアーを行います。 LCA を求めたい場合は、LCA $= true$ を指定してください。

制約

g は root を根とした根付き木または木

計算量

LCA $= false$ : $\Theta(N)$
LCA $= true$ : $\mathcal{O}(N \log{\log{N}})$

メンバ関数

int size()

グラフの頂点数 $N$ を返します。

計算量

$\Theta(1)$

int par(int v)

頂点 $v$ の親を返します。存在しなければ $-1$ を返します。

制約

$0 \leq v < N$

計算量

$\Theta(1)$

int tree_id(int v)

頂点 $v$ が属する木の ID を返します。 ID は各木に対して $0$ から順に割り振られます。

制約

$0 \leq v < N$

計算量

$\Theta(1)$

int tree_cnt()

グラフ g に含まれる木の個数を返します。

計算量

$\Theta(1)$

int trees()

グラフ g に含まれる木の根を ID の昇順に返します。

計算量

$\Theta(1)$

int heavy(int v)

頂点 v が属する heavy-edge の ID を返します。
ID は各 heavy-edge に対して $0$ から順に割り振られます。

計算量

$\Theta(1)$

int head(int k)

heavy-edge k に含まれる頂点の内、最も根側の頂点番号を返します。

制約

$0 \leq k <$ heavy_size()

計算量

$\Theta(1)$

int heavy_size()

heavy-edge の本数を返します。

計算量

$\Theta(1)$

int heavy_size(int k)

heavy-edge k に含まれるの頂点数を返します。

制約

$0 \leq k <$ heavy_size()

計算量

$\Theta(1)$

int heavy_depth(int k)

heavy-edge k から根が属する heavy-edge 間のパス上に含まれる heavy-edge の個数 $-1$ を返します。

制約

$0 \leq k <$ heavy_size()

計算量

$\Theta(1)$

int in(int v)

頂点 v に入ったときの時刻を返します。ただし、時刻は頂点に到達した際に増加します。

制約

$0 \leq v < N$

計算量

$\Theta(1)$

int out(int v)

頂点 v から出たときの時刻を返します。ただし、時刻は頂点に到達した際に増加します。

制約

$0 \leq v < N$

計算量

$\Theta(1)$

const std::vector<std::vector<int>> & par_dblng()

次のようなテーブルを返します。

$[i][j] :=$ heavy-edge $j$ から $2^i$ 回根方向に heavy-edge を登ったすぐの頂点番号(存在しなければ根の番号)

制約

LCA $= true$

計算量

$\Theta(1)$

std::pair<int, int> lca_heavy(int x, int y)

頂点 $x, y$ から根側に移動して同じ heavy-edge 内となるような最も移動回数の和が小さい頂点位置の組を返します。

制約

LCA $= true$
$0 \leq x, y < N$
$x, y$ は同じ木に属する

計算量

$\mathcal{O}(\log{\log{N}})$

lca(int x, int y)

頂点 $x, y$ の最近共通祖先を返します。

制約

LCA $= true$
$0 \leq x, y < N$
$x, y$ は同じ木に属する

計算量

$\mathcal{O}(\log{\log{N}})$

使用例

#include <bits/stdc++.h>
#include "GraphTheory/HeavyLightDecomposition.hpp"
using namespace std;

int main() {
	HeavyLightDecomposition::Graph g(9);
	//            1
	//       2        3
	//    0     4         5
	// 6       7 8
	g[1].emplace_back(2);
	g[1].emplace_back(3);
	g[2].emplace_back(0);
	g[2].emplace_back(4);
	g[0].emplace_back(6);
	g[4].emplace_back(7);
	g[4].emplace_back(8);
	g[3].emplace_back(5);
	
	g[5].emplace_back(3); // 逆辺があっても良い
	
	HeavyLightDecomposition hld(g, 1, true);
	
	cout << "size() = " << hld.size() << endl; // 9
	cout << "heavy_size() = " << hld.heavy_size() << endl; // 4
	cout << "par: ";
	// 2 -1 1 1 2 3 0 4 4
	for (int i = 0; i < hld.size(); ++i) cout << hld.par(i) << " \n"[i + 1 == hld.size()];
	
	cout << "heavy: ";
	// 1 0 0 3 0 3 1 0 2
	for (int i = 0; i < hld.size(); ++i) cout << hld.heavy(i) << " \n"[i + 1 == hld.size()];
	// heavy 0 : [1, 2, 4, 8]
	// heavy 1 : [0, 6]
	// heavy 2 : [8]
	// heavy 3 : [3, 5]
	//           heavy-0
	// heavy-1   heavy-2   heavy-3
	cout << "head: ";
	// 1 0 8 3
	for (int i = 0; i < hld.heavy_size(); ++i) cout << hld.head(i) << " \n"[i + 1 == hld.heavy_size()];
	cout << "heavy_size: ";
	// 4 2 1 2
	for (int i = 0; i < hld.heavy_size(); ++i) cout << hld.heavy_size(i) << " \n"[i + 1 == hld.heavy_size()];
	cout << "heavy_size: ";
	// 0 1 1 1
	for (int i = 0; i < hld.heavy_size(); ++i) cout << hld.heavy_depth(i) << " \n"[i + 1 == hld.heavy_size()];
	
	cout << "in: ";
	// 5 0 1 7 2 8 6 3 4
	for (int i = 0; i < hld.size(); ++i) cout << hld.in(i) << " \n"[i + 1 == hld.size()];
	cout << "out: ";
	// 7 9 7 9 5 9 7 4 5
	for (int i = 0; i < hld.size(); ++i) cout << hld.out(i) << " \n"[i + 1 == hld.size()];
	
	{
		auto [x, y] = hld.lca_heavy(1, 4);
		cout << "lca_heavy(1, 4) = (" << x << ", " << y << ")\n"; // (1, 4)
	}
	{
		auto [x, y] = hld.lca_heavy(2, 6);
		cout << "lca_heavy(2, 6) = (" << x << ", " << y << ")\n"; // (2, 2)
	}
	{
		auto [x, y] = hld.lca_heavy(6, 5);
		cout << "lca_heavy(6, 5) = (" << x << ", " << y << ")\n"; // (2, 1)
	}
	
	cout << "lca(2, 3) = " << hld.lca(2, 3) << endl; // 1
	cout << "lca(6, 8) = " << hld.lca(6, 8) << endl; // 2
	cout << "lca(4, 8) = " << hld.lca(4, 8) << endl; // 4
}

参考

2020/04/19: https://qiita.com/ageprocpp/items/8dfe768218da83314989
2020/04/19: https://math314.hateblo.jp/entry/2014/06/24/220107
2020/09/18: https://codeforces.com/blog/entry/53170

Required by

重軽分解 ( HL 分解) クエリ (GraphTheory/HeavyLightDecomposition_Query.hpp)

Verified with

Code

#ifndef INCLUDE_GUARD_HEAVY_LIGHT_DECOMPOSITION_HPP
#define INCLUDE_GUARD_HEAVY_LIGHT_DECOMPOSITION_HPP

#include <vector>
#include <cassert>
#include <stack>
#include <utility>
#include <algorithm>

/**
 * @brief https://tkmst201.github.io/Library/GraphTheory/HeavyLightDecomposition.hpp
 */
struct HeavyLightDecomposition {
	using Graph = std::vector<std::vector<int>>;
	
private:
	int n;
	std::vector<int> par_;
	std::vector<int> heavy_, head_, heavy_size_, heavy_depth_;
	std::vector<int> tree_id_, roots_;
	std::vector<int> in_, out_;
	std::vector<std::vector<int>> par_dblng_;
	bool LCA;
	
public:
	HeavyLightDecomposition(const Graph & g, bool LCA = false)
		: HeavyLightDecomposition(g, -1, LCA) {}
	
	HeavyLightDecomposition(const Graph & g, int root, bool LCA)
		: n(g.size()), par_(n, -1), heavy_(n, -1), tree_id_(n, -1), in_(n, -1), out_(n, -1), LCA(LCA) {
		std::vector<int> sub_size(n, 0), next(n, -1);
		for (int i = 0; i < n; ++i) {
			if (tree_id_[i] != -1) continue;
			if (root != -1 && i != root) continue;
			tree_id_[i] = roots_.size();
			std::stack<int> stk;
			stk.emplace(i);
			while (!stk.empty()) {
				const int u = stk.top();
				stk.pop();
				if (sub_size[u]) {
					int mx_size = 0;
					for (int v : g[u]) {
						if (v == par_[u]) continue;
						sub_size[u] += sub_size[v];
						if (mx_size < sub_size[v]) mx_size = sub_size[v], next[u] = v;
					}
					continue;
				}
				sub_size[u] = 1;
				stk.emplace(u);
				for (int v : g[u]) {
					assert(0 <= v && v < n);
					assert(v != u);
					if (v == par_[u]) continue;
					par_[v] = u;
					tree_id_[v] = roots_.size();
					stk.emplace(v);
				}
			}
			roots_.emplace_back(i);
		}
		int euc = 0;
		for (int r : roots_) {
			heavy_[r] = head_.size();
			head_.emplace_back(r);
			heavy_size_.emplace_back(1);
			heavy_depth_.emplace_back(0);
			std::stack<std::pair<int, int>> stk;
			stk.emplace(r, 0);
			while (!stk.empty()) {
				const auto [u, i] = stk.top();
				stk.pop();
				if (i < static_cast<int>(g[u].size())) {
					stk.emplace(u, i + 1);
					const int v = g[u][i];
					if (v != par_[u] && v != next[u]) {
						heavy_[v] = head_.size();
						head_.emplace_back(v);
						heavy_size_.emplace_back(1);
						heavy_depth_.emplace_back(heavy_depth_[heavy_[u]] + 1);
						stk.emplace(v, 0);
					}
				}
				if (i == 0) {
					in_[u] = euc++;
					const int v = next[u];
					if (v != -1) {
						heavy_[v] = heavy_[u];
						++heavy_size_[heavy_[u]];
						stk.emplace(v, 0);
					}
				}
				if (i == static_cast<int>(g[u].size())) out_[u] = euc;
			}
		}
		if (!LCA) return;
		int max_depth = *std::max_element(begin(heavy_depth_), end(heavy_depth_));
		int lglg_n = 0;
		while ((1 << lglg_n) <= max_depth) ++lglg_n;
		par_dblng_.assign(lglg_n + 1, std::vector<int>(heavy_size(), -1));
		for (int i = 0; i < heavy_size(); ++i) par_dblng_[0][i] = par_[head_[i]] == -1 ? head_[i] : par_[head_[i]];
		for (int i = 0; i < lglg_n; ++i) {
			for (int j = 0; j < heavy_size(); ++j) {
				par_dblng_[i + 1][j] = par_dblng_[i][heavy_[par_dblng_[i][j]]];
			}
		}
	}
	
	int size() const noexcept {
		return n;
	}
	
	int par(int v) const noexcept {
		assert(0 <= v && v < size());
		return par_[v];
	}
	
	int tree_id(int v) const noexcept {
		assert(0 <= v && v < size());
		return tree_id_[v];
	}
	
	int tree_cnt() const noexcept {
		return roots_.size();
	}
	
	const std::vector<int> & trees() const noexcept {
		return roots_;
	}
	
	int heavy(int v) const noexcept {
		assert(0 <= v && v < size());
		return heavy_[v];
	}
	
	int head(int k) const noexcept {
		assert(0 <= k && k < heavy_size());
		return head_[k];
	}
	
	int heavy_size() const noexcept {
		return head_.size();
	}
	
	int heavy_size(int k) const noexcept {
		assert(0 <= k && k < heavy_size());
		return heavy_size_[k];
	}
	
	int heavy_depth(int k) const noexcept {
		assert(0 <= k && k < heavy_size());
		return heavy_depth_[k];
	}
	
	int in(int v) const noexcept {
		assert(0 <= v && v < size());
		return in_[v];
	}
	
	int out(int v) const noexcept {
		assert(0 <= v && v < size());
		return out_[v];
	}
	
	const std::vector<std::vector<int>> & par_dblng() const noexcept {
		assert(LCA);
		return par_dblng_;
	}
	
	std::pair<int, int> lca_heavy(int x, int y) const noexcept {
		assert(LCA);
		assert(0 <= x && x < size());
		assert(0 <= y && y < size());
		assert(tree_id_[x] == tree_id_[y]);
		if (heavy_[x] == heavy_[y]) return {x, y};
		const bool isswap = heavy_depth_[heavy_[x]] < heavy_depth_[heavy_[y]];
		if (isswap) std::swap(x, y);
		const int diff = heavy_depth_[heavy_[x]] - heavy_depth_[heavy_[y]];
		for (int i = 0; i < static_cast<int>(par_dblng_.size()); ++i) if (diff >> i & 1) x = par_dblng_[i][heavy_[x]];
		if (heavy_[x] == heavy_[y]) return isswap ? std::make_pair(y, x) : std::make_pair(x, y);
		for (int i = par_dblng_.size() - 1; i >= 0; --i) {
			const int p1 = par_dblng_[i][heavy_[x]], p2 = par_dblng_[i][heavy_[y]];
			if (heavy_[p1] != heavy_[p2]) x = p1, y = p2;
		}
		x = par_dblng_[0][heavy_[x]];
		y = par_dblng_[0][heavy_[y]];
		return isswap ? std::make_pair(y, x) : std::make_pair(x, y);
	}
	
	int lca(int x, int y) {
		assert(LCA);
		assert(0 <= x && x < size());
		assert(0 <= y && y < size());
		assert(tree_id_[x] == tree_id_[y]);
		const auto [a, b] = lca_heavy(x, y);
		return in_[a] < in_[b] ? a : b;
	}
};

#endif // INCLUDE_GUARD_HEAVY_LIGHT_DECOMPOSITION_HPP

#line 1 "GraphTheory/HeavyLightDecomposition.hpp"



#include <vector>
#include <cassert>
#include <stack>
#include <utility>
#include <algorithm>

/**
 * @brief https://tkmst201.github.io/Library/GraphTheory/HeavyLightDecomposition.hpp
 */
struct HeavyLightDecomposition {
	using Graph = std::vector<std::vector<int>>;
	
private:
	int n;
	std::vector<int> par_;
	std::vector<int> heavy_, head_, heavy_size_, heavy_depth_;
	std::vector<int> tree_id_, roots_;
	std::vector<int> in_, out_;
	std::vector<std::vector<int>> par_dblng_;
	bool LCA;
	
public:
	HeavyLightDecomposition(const Graph & g, bool LCA = false)
		: HeavyLightDecomposition(g, -1, LCA) {}
	
	HeavyLightDecomposition(const Graph & g, int root, bool LCA)
		: n(g.size()), par_(n, -1), heavy_(n, -1), tree_id_(n, -1), in_(n, -1), out_(n, -1), LCA(LCA) {
		std::vector<int> sub_size(n, 0), next(n, -1);
		for (int i = 0; i < n; ++i) {
			if (tree_id_[i] != -1) continue;
			if (root != -1 && i != root) continue;
			tree_id_[i] = roots_.size();
			std::stack<int> stk;
			stk.emplace(i);
			while (!stk.empty()) {
				const int u = stk.top();
				stk.pop();
				if (sub_size[u]) {
					int mx_size = 0;
					for (int v : g[u]) {
						if (v == par_[u]) continue;
						sub_size[u] += sub_size[v];
						if (mx_size < sub_size[v]) mx_size = sub_size[v], next[u] = v;
					}
					continue;
				}
				sub_size[u] = 1;
				stk.emplace(u);
				for (int v : g[u]) {
					assert(0 <= v && v < n);
					assert(v != u);
					if (v == par_[u]) continue;
					par_[v] = u;
					tree_id_[v] = roots_.size();
					stk.emplace(v);
				}
			}
			roots_.emplace_back(i);
		}
		int euc = 0;
		for (int r : roots_) {
			heavy_[r] = head_.size();
			head_.emplace_back(r);
			heavy_size_.emplace_back(1);
			heavy_depth_.emplace_back(0);
			std::stack<std::pair<int, int>> stk;
			stk.emplace(r, 0);
			while (!stk.empty()) {
				const auto [u, i] = stk.top();
				stk.pop();
				if (i < static_cast<int>(g[u].size())) {
					stk.emplace(u, i + 1);
					const int v = g[u][i];
					if (v != par_[u] && v != next[u]) {
						heavy_[v] = head_.size();
						head_.emplace_back(v);
						heavy_size_.emplace_back(1);
						heavy_depth_.emplace_back(heavy_depth_[heavy_[u]] + 1);
						stk.emplace(v, 0);
					}
				}
				if (i == 0) {
					in_[u] = euc++;
					const int v = next[u];
					if (v != -1) {
						heavy_[v] = heavy_[u];
						++heavy_size_[heavy_[u]];
						stk.emplace(v, 0);
					}
				}
				if (i == static_cast<int>(g[u].size())) out_[u] = euc;
			}
		}
		if (!LCA) return;
		int max_depth = *std::max_element(begin(heavy_depth_), end(heavy_depth_));
		int lglg_n = 0;
		while ((1 << lglg_n) <= max_depth) ++lglg_n;
		par_dblng_.assign(lglg_n + 1, std::vector<int>(heavy_size(), -1));
		for (int i = 0; i < heavy_size(); ++i) par_dblng_[0][i] = par_[head_[i]] == -1 ? head_[i] : par_[head_[i]];
		for (int i = 0; i < lglg_n; ++i) {
			for (int j = 0; j < heavy_size(); ++j) {
				par_dblng_[i + 1][j] = par_dblng_[i][heavy_[par_dblng_[i][j]]];
			}
		}
	}
	
	int size() const noexcept {
		return n;
	}
	
	int par(int v) const noexcept {
		assert(0 <= v && v < size());
		return par_[v];
	}
	
	int tree_id(int v) const noexcept {
		assert(0 <= v && v < size());
		return tree_id_[v];
	}
	
	int tree_cnt() const noexcept {
		return roots_.size();
	}
	
	const std::vector<int> & trees() const noexcept {
		return roots_;
	}
	
	int heavy(int v) const noexcept {
		assert(0 <= v && v < size());
		return heavy_[v];
	}
	
	int head(int k) const noexcept {
		assert(0 <= k && k < heavy_size());
		return head_[k];
	}
	
	int heavy_size() const noexcept {
		return head_.size();
	}
	
	int heavy_size(int k) const noexcept {
		assert(0 <= k && k < heavy_size());
		return heavy_size_[k];
	}
	
	int heavy_depth(int k) const noexcept {
		assert(0 <= k && k < heavy_size());
		return heavy_depth_[k];
	}
	
	int in(int v) const noexcept {
		assert(0 <= v && v < size());
		return in_[v];
	}
	
	int out(int v) const noexcept {
		assert(0 <= v && v < size());
		return out_[v];
	}
	
	const std::vector<std::vector<int>> & par_dblng() const noexcept {
		assert(LCA);
		return par_dblng_;
	}
	
	std::pair<int, int> lca_heavy(int x, int y) const noexcept {
		assert(LCA);
		assert(0 <= x && x < size());
		assert(0 <= y && y < size());
		assert(tree_id_[x] == tree_id_[y]);
		if (heavy_[x] == heavy_[y]) return {x, y};
		const bool isswap = heavy_depth_[heavy_[x]] < heavy_depth_[heavy_[y]];
		if (isswap) std::swap(x, y);
		const int diff = heavy_depth_[heavy_[x]] - heavy_depth_[heavy_[y]];
		for (int i = 0; i < static_cast<int>(par_dblng_.size()); ++i) if (diff >> i & 1) x = par_dblng_[i][heavy_[x]];
		if (heavy_[x] == heavy_[y]) return isswap ? std::make_pair(y, x) : std::make_pair(x, y);
		for (int i = par_dblng_.size() - 1; i >= 0; --i) {
			const int p1 = par_dblng_[i][heavy_[x]], p2 = par_dblng_[i][heavy_[y]];
			if (heavy_[p1] != heavy_[p2]) x = p1, y = p2;
		}
		x = par_dblng_[0][heavy_[x]];
		y = par_dblng_[0][heavy_[y]];
		return isswap ? std::make_pair(y, x) : std::make_pair(x, y);
	}
	
	int lca(int x, int y) {
		assert(LCA);
		assert(0 <= x && x < size());
		assert(0 <= y && y < size());
		assert(tree_id_[x] == tree_id_[y]);
		const auto [a, b] = lca_heavy(x, y);
		return in_[a] < in_[b] ? a : b;
	}
};

重軽分解 ( HL 分解) (GraphTheory/HeavyLightDecomposition.hpp)

概要

コンストラクタ

HeavyLightDecomposition(const Graph & g, bool LCA = false)

HeavyLightDecomposition(const Graph & g, int root, bool LCA = false)

メンバ関数

int size()

int par(int v)

int tree_id(int v)

int tree_cnt()

int trees()

int heavy(int v)

int head(int k)

int heavy_size()

int heavy_size(int k)

int heavy_depth(int k)

int in(int v)

int out(int v)

const std::vector<std::vector<int>> & par_dblng()

std::pair<int, int> lca_heavy(int x, int y)

lca(int x, int y)

使用例

参考

Required by

Verified with

Code

重軽分解 ( HL 分解)
(GraphTheory/HeavyLightDecomposition.hpp)