Codeforces Round #518 (Div. 1) [Thanks, Mail.Ru!] - B. Multihedgehog
解説
イメージとしては重心分解です！
1-multihedgehogにおけるcenterは木の中心になっています。(そしてこの木の直径は2です。)
2-multihedgehogになると木の直径が2つふえるだけで、centerの位置はかわりません。
一般に-multihedgehogから
-multihedgehogになるとcenterの位置は変わらず、直径が2ずつ増えていきます
よって-multihedgehogかどうかを判定するには
木の直径が偶数
木の中心の次数が3以上
をまずチェックします。そうするとあとはこのcenterを消して、分解した先が-multihedgehogかどうかをチェックするのであとはこれを再帰的に繰り返していけばいいです。
木の大きさが1/3以下ずつになっていくので、重心分解と同様の理由で高速に動きます。
提出コード
ちょっと読みにくいので、簡単に関数名だけ説明します。
- uni : 1--multihedgehogチェック用で連結成分の全ての次数を返します。
- cn: 連結成分をかえします。
- bfs: 直径を求める際に利用しているbfsです。
- dfs: 上記で説明した再帰的な処理をやっています。
