きままにものづくり

日々の気付いたことなんかを書いてます。

ARC028 C問題

問題


C: 高橋王国の分割統治 - AtCoder Regular Contest 028 | AtCoder

解法

ツリー構造になっているので、子となる頂点をルートとした際のサブツリーの要素数をDFSで求めていく。バランス値は、子のサブツリーの要素数と、自身をルートとした際のサブツリーの要素数とNの差分の中で最大なものとなる。自身をルートとした際のサブツリーの要素数は子のサブツリーの要素数の総和に1を足したものとなる。

計算量

 O(N)

コード