Centroid Decomposition (木の重心分解) (graph/centroid_decomposition.cpp)

• View this file on GitHub
• View document part on GitHub
• Last update: 2024-07-16 15:50:19+09:00

なにこれ

木構造の重心を求める．

コンストラクタ

• centroid_decomposition(E)：木または森を表す隣接リスト E について前処理を行う．

メンバ関数

• get(x, tsize)：頂点 x が含まれるサイズ tsize の木について，重心および重心分解後の各部分木に含まれる頂点とサイズの配列を返す．
• del(x)：頂点 x を削除する．

計算量

E に含まれる頂点数を $n$ とする．

• コンストラクタ：$O(n)$

対象となる木のサイズを $m$ とする．

• get(x, tsize)：$O(m)$
• del(x)：$O(1)$

重心分解の再帰について

重心分解後の各部分木について，get() の返り値に含まれる頂点とサイズの情報を用いることで再帰的に重心分解を繰り返すことができる．

1レイヤーの重心分解につき部分木の最大サイズは半分以下となるため，頂点数1の木になるまで重心分解したときのレイヤー数は $O(\log n)$ である． また，del(x) で重心を論理削除すれば E および subsizes を再初期化する必要はないため，1つのインスタンスを使い回すことができる． これは全体 $O(n \log n)$ で実行することができる．

実装例については atc_abc291_ex や cf_321_c を参照されたい．

参考

• https://qiita.com/drken/items/4b4c3f1824339b090202

Depends on

• 2D-Array( $2$ 次元配列) (structure/2d_array.cpp)

Verified with

• test/atc_abc291_ex.cpp
• test/cf_321_c.cpp

Code

#pragma once

#ifndef call_include
#define call_include
#include <bits/stdc++.h>
using namespace std;
#endif

#include "../structure/2d_array.cpp"

struct centroid_decomposition {
private:
	int n;
	v2d<int> &E;
	vector<int> deleted;
	vector<int> subsizes;
	int found_cent;

	int centroid = -1;
	vector<pair<int, int>> subtrees;

public:
	centroid_decomposition(v2d<int> &E) : E(E), n(E.size()), deleted(n, 0), subsizes(n){};

private:
	int dfs(int x, int tsize, int prev = -1) {
		int size = 1, cent_flag = 1;
		for(int i = 0; i < E[x].size(); i++) {
			int nx = E[x][i];
			if(deleted[nx] or nx == prev) continue;
			int chsize = dfs(nx, tsize, x);
			if(found_cent) return -1;
			if(chsize > tsize / 2) cent_flag = 0;
			size += chsize;
		}
		if(tsize - size > tsize / 2) cent_flag = 0;
		if(cent_flag) {
			found_cent = 1;
			centroid = x;
			for(int i = 0; i < E[x].size(); i++) {
				int nx = E[x][i];
				if(deleted[nx]) continue;
				if(nx == prev) {
					subtrees.emplace_back(nx, tsize - size);
				}
				else {
					subtrees.emplace_back(nx, subsizes[nx]);
				}
			}
		}

		return subsizes[x] = size;
	}

public:
	pair<int, vector<pair<int, int>>> get(int x, int tsize) {
		subtrees.clear();
		found_cent = 0;
		dfs(x, tsize);
		return pair(centroid, subtrees);
	}

	inline void del(int x) {
		deleted[x] = 1;
	}
};

#line 2 "graph/centroid_decomposition.cpp"

#ifndef call_include
#define call_include
#include <bits/stdc++.h>
using namespace std;
#endif

#line 2 "structure/2d_array.cpp"

#ifndef call_include
#define call_include
#include <bits/stdc++.h>
using namespace std;
#endif

template<typename T> struct v2d {
private:
	vector<vector<T>> m;

public:
	v2d() {}
	v2d(int h, int w) : m(h, vector<T>(w)) {}
	v2d(int h, int w, const T &init) : m(h, vector<T>(w, init)) {}
	v2d(const initializer_list<initializer_list<T>> m_init) : m(m_init.begin(), m_init.end()) {}

	void assign(int h, int w) {
		m.assign(h, vector<T>(w));
	}
	void assign(int h, int w, const T init) {
		m.assign(h, vector<T>(w, init));
	}

	inline int size() const {
		return m.size();
	}

	void in() {
		for(vector<T> &v : m)
			for(T &val : v) cin >> val;
	}
	void in(int h, int w) {
		m.resize(h, vector<T>(w));
		in();
	}

	void out() {
		int h = m.size();
		for(vector<T> &v : m) {
			int sz = v.size();
			for(int j = 0; j < sz; j++) {
				cout << v[j] << (j == sz - 1 ? '\n' : ' ');
			}
		}
		cout << flush;
	}

	inline vector<T> &operator[](int idx) {
		assert(0 <= idx && idx < m.size());
		return m[idx];
	}

	bool rangeout(int x, int y) {
		if(x < 0 || y < 0 || x >= size() || y >= m[x].size()) return true;
		return false;
	}
};
#line 10 "graph/centroid_decomposition.cpp"

struct centroid_decomposition {
private:
	int n;
	v2d<int> &E;
	vector<int> deleted;
	vector<int> subsizes;
	int found_cent;

	int centroid = -1;
	vector<pair<int, int>> subtrees;

public:
	centroid_decomposition(v2d<int> &E) : E(E), n(E.size()), deleted(n, 0), subsizes(n){};

private:
	int dfs(int x, int tsize, int prev = -1) {
		int size = 1, cent_flag = 1;
		for(int i = 0; i < E[x].size(); i++) {
			int nx = E[x][i];
			if(deleted[nx] or nx == prev) continue;
			int chsize = dfs(nx, tsize, x);
			if(found_cent) return -1;
			if(chsize > tsize / 2) cent_flag = 0;
			size += chsize;
		}
		if(tsize - size > tsize / 2) cent_flag = 0;
		if(cent_flag) {
			found_cent = 1;
			centroid = x;
			for(int i = 0; i < E[x].size(); i++) {
				int nx = E[x][i];
				if(deleted[nx]) continue;
				if(nx == prev) {
					subtrees.emplace_back(nx, tsize - size);
				}
				else {
					subtrees.emplace_back(nx, subsizes[nx]);
				}
			}
		}

		return subsizes[x] = size;
	}

public:
	pair<int, vector<pair<int, int>>> get(int x, int tsize) {
		subtrees.clear();
		found_cent = 0;
		dfs(x, tsize);
		return pair(centroid, subtrees);
	}

	inline void del(int x) {
		deleted[x] = 1;
	}
};

Back to top page