This documentation is automatically generated by competitive-verifier/competitive-verifier
木構造の重心を求める.
centroid_decomposition(E)
:木または森を表す隣接リスト E
について前処理を行う.get(x, tsize)
:頂点 x
が含まれるサイズ tsize
の木について,重心および重心分解後の各部分木に含まれる頂点とサイズの配列を返す.del(x)
:頂点 x
を削除する.E
に含まれる頂点数を $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
を参照されたい.
#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;
}
};