centroid.hpp ファイル

#include "../../../kyopro_library/template.hpp"

[ソースコード]

関数
int	TreeCentroid (const vector< vector< int > > &g, int root, vector< int > &seen, vector< int > &sz)
	重心分解

関数詳解

TreeCentroid()

int TreeCentroid	(	const vector< vector< int > > &	g,
		int	root,
		vector< int > &	seen,
		vector< int > &	sz )

重心分解

引数

seen	探索済みフラグ
sz	各頂点の部分木のサイズ

vector<int> sz(N);
vector<bool> seen(N);
 
auto centroid_decomposition = [&](auto self, int root) -> void {
    int centroid = TreeCentroid(g, root, seen, sz);
    seen[centroid] = true;
 
    // ここに処理を書く
 
    for (int nxt : g[centroid]) {
        if (seen[nxt]) continue;
        self(self, nxt);
    }
};
centroid_decomposition(centroid_decomposition, 0);

centroid.hpp の 27 行目に定義があります。