Codeforces Round #670 (Div. 2) C. Link Cut Centroids

どうやって証明ができるのかわからない。
気づき

問題文に不可能な場合がないので、連結成分の最大の最小は2以下らしい
2つの場合は連結成分の大きさが等しいので、どちらかから一つの頂点を引いて、他方に一つ足せば良い

この問題は「木の重心」がキーワードみたいです。

ある頂点を取り除いて、分割された木のサイズが $\frac{N}{2}$ 以下になるとき、取り除いた頂点を「木の重心」という。
重心は2つ以下である
重心が2つある時、それらは隣接する

これらの性質と気付きによって、問題は解けます。
木の重心は木DPで求まる。

参考

……

が、これは頭が良すぎるので、もう少し泥臭いことをする。
上は証明が見つかるので、事実として受け入れます。
実際は未証明のまま雰囲気でときました（よくない）。

解法

任意の頂点 $i$ を取り除いて分割された木のサイズの最大値を全て求める( $S_i$ とする)
$S$ をソートする
$S$ の最小値が一つなら任意の辺を同じ場所で付け替える（木の変更をしない）
$S$ の最小値が2つのとき、片方の木の末端を他方に付け替える

1.について、
根付き木と考えて、任意の頂点について、下にある頂点の数を記録する。
これは基本的なDFSで解ける。
この結果から任意の頂点 $P$ を取り除いたときの、分割された木の連結成分の大きさが求まる。
( $\because$ 任意の頂点の子の属する連結成分のサイズは、子がの子の下にある頂点数を記録しているので、それ＋1が連結成分のサイズになる。親が属する連成分のサイズは、自分の下にある頂点数と自分自身（ $+1$ ）を $N$ から引いたサイズになる)

4.について
1.で求めた配列を $S$ （ソート済み）とする。
最大値の最小値が等しいとき、木はこうなっていることが予想される（fig.2）。

これは非常に感覚的だが、選択する頂点を動かすと連結成分の数は、片方が増えて、片方が減るので、直感的には正しそうに見える（fig.3）（実際は木の重心についてを参照）
$S$ より、木の重心として取り除かれる頂点は求まっているので、それぞれの頂点を $p1$ , $p2$ として、 $p1$ から $p2$ （親とみなして）の方向へ行かないように、BFSまたはDFSをして、 $p1$ より下にある末端の頂点をもとめて、 $p2$ に繋げば良い。