木のCentroid Decomposition

分割統治っぽくなって，頂点数Nの部分木にたいしてO(f(n))の計算量がかかるとすると，全体の計算量はCentroid DecompositionをするとO(f(n) log n)になってはやい．

追記：コードに誤りがあったので修正しました．まだあるかもしれない

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
typedef pair<int, int> P;
#define to first
#define length second
const int INF = 1 << 29;
const int MAXN = 10000;
vector<P> G[MAXN];
bool centroid[MAXN];
int subtree_size[MAXN];

//部分木の大きさを計算
int compute_subtree_size(int v, int p){
	int c = 1;
	for(int i=0;i<G[v].size();i++){
		int w = G[v][i].to;
		if(w==p || centroid[w]) continue;
		c+=compute_subtree_size(w,v);
	}
	subtree[v] = c;
	return c;
}
//重心を求める
pair<int,int> search_centroid(int v, int p, int t){
	pair<int,int> res = make_pair(INF, -1);
	int s=1, m=0;
	for(int i=0;i<G[v].size();i++){
		int w = G[v][i].to;
		if(w==p || centroid[w]) continue;
		res = min(res, search(w,v,t));

		m=max(m,subtree[w]);
		s+=subtree[w];
	}
	m=max(m, t-s);
	res = min(res, make_pair(m,v));
	return res;
}

void solve_subproblem(int v){
	compute_subtree_size(v, -1);
	int s = search_centroid(v,-1,subtree[v]);
	centroid[s] = true;

	for(int i=0;i<G[s].size();i++){
		if(centroid[G[s][i].to])continue;
		solve_subproblem(G[s][i].to);
	}
    
	//ここに処理をかく

	centroid[s] = false;
}
void solve(){
	solve_subproblem(0);
}