Cenroid Decomposition
コードについての説明
重心分解と呼ばれる, 重心で木を再帰的に分解していくことで高さが $\O (\log n)$ になるような分解を行うアルゴリズムである.
各階層であつかう木構造をすべて合わせても空間計算量が $\O (n \log n)$ なのですべての木について DFS なりの探索を行うことが可能.
申しわけ程度に説明を書いているけれども結局 わかりやすく説明してくれている記事 を参考にする方が圧倒的に理解しやすい.
多くの問題は重心分解をただやるだけでなく前処理として行ったあとに問題に応じた操作を行う. 一応親子関係を伝播させることもできるが,基本的には親子関係は壊れてしまうので部分木についての条件など元の木上での親子関係が必要となる問題については使えない. 以下に挙げた verify 問題みたいなものについては有効である.
(関数)
add_edge(): 辺を追加する
build(): 重心分解を行う
時間計算量: $\O (n \log n)$
コード
class CentroidDecomposition
{
private:
int V;
vector<vector<int> > G;
vector<bool> used;
//sz:重心分解後の最大部分木に含まれる頂点の数(自分を含める)
//par:重心分解後の親の頂点
vector<int> sz, par;
//部分木のサイズを計算
void calcSize(int u,int p){
sz[u] = 1;
for(int v : G[u]){
if(!used[v] && v != p){
calcSize(v,u);
sz[u] += sz[v];
}
}
}
void cdBuild(int u,int p){
calcSize(u,-1);
int tot = sz[u];
bool ok = false;
int pp = -1;
//いま見ている部分木での重心を見つける
while(!ok){
ok = true;
for(int v : G[u]){
if(!used[v] && v != pp && 2*sz[v] > tot){
pp = u, u = v, ok = false;
break;
}
}
}
par[u] = p;
//何らかの操作
used[u] = true;
//深さ優先でたどる
for(int v : G[u]){
if(!used[v]){
cdBuild(v,u);
}
}
}
public:
CentroidDecomposition(int node_size) : V(node_size), G(V), used(V, false)
, sz(V, 0), par(V, -1){}
void add_edge(int u,int v){
G[u].push_back(v), G[v].push_back(u);
}
void build(){
cdBuild(0,-1);
}
};