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

#はじめに
重心分解は25行程度でかけます
(わかりやすい様にコメント付加してたら30行程度になってしまいました)
ポイントは重心分解によって出来る木をBFSでなくDFSで潜ることです！！！

Centroid_Decomposition.cpp

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(auto e:g[n]){
        if(p==e)continue;
        auto t=dfs(e,n,sz,root);
        res+=t;
        if(t>sz/2)b=0;
    }
    if(!b||sz-res>sz/2)return res;//重心で無いなら部分木のサイズを返す

    //重心を登録
    if(root!=-1)ch[root].emplace_back(n);
    else s=n;
    v.push_back(n);
    used[n]=1;

    //重心分解後の木で自身の子となる重心を探す
    //dfs(e,n,inf,n)では部分木のサイズを求めてる
    //(szをinfにすると当然重心が見つからないため部分木のサイズが返る)
    for(auto e:g[n])dfs(e,n,dfs(e,n,inf,n),n);
    
    //重心はすでに見つかったためinf=MAX_SZ*2を返す
    return inf;
}

使用方法

グラフを g に隣接リスト表示で初期化したのち dfs(0,-1,(頂点サイズ),-1); を呼び出します。
vには重心分解後の木をdfsした結果が入ります(なくてもいいかも)
chには、重心分解後の木における子供が入ります
sは重心分解後の木の根が入ります
dfsの挙動は見たままです。は?(質問がある方はtwitterまで)

verify

Ciel the Commander -codeforces
回答例