【競技プログラミング】重心分解を25行で書く方法 - Qiita

#はじめに 重心分解は25行程度でかけます (わかりやすい様にコメント付加してたら30行程度になってしまいました) ポイントは重心分解によって出来る木をBFSでなくDFSで潜ることです！！！ constexpr int MAX_SZ=1<<20; array<vector<int>,MAX_SZ>g;//元の木の隣接リスト array<int,MAX_SZ>used;//重心が確定したか vector<int>v;//重心分解後の木のDFS順の列 array<vector<int>,MAX_SZ>ch;//重心分解後の木の親子関係 int s;//重心分解後の木の根 int dfs(int n,int p,int sz,int root){ constexpr int inf=MAX_SZ*2; if(used[n])return 0; bool b=1; int res=1; for(a