木のセントロイドを求める
頂点数が
v の木が与えられています。この木のセントロイドを見つけることが課題です。木のセントロイドとは、その頂点を取り除いたとき、残るすべての部分木のサイズが最大でも ノード以下になるような頂点のことを指します。入力
最初の行には、整数
v (1 ≤ v ≤ 100 000) が与えられます。続く
v-1 行には、整数の組 v1、v2 (1 ≤ v1, v2 ≤ v) が与えられます。これは頂点 v1 と頂点 v2 がお互いに接続されていることを示します。出力
与えられた木のセントロイドを出力してください。セントロイドが複数存在する場合は、そのうちのいずれかを出力して構いません。
例
Input | 入力 |
3
1 2
1 3 | 1 |
5
1 2
2 3
3 4
3 5 | 3 |
ヒント
各ノードに対して、そのノードを根とする部分木のサイズ（子ノードの数）を計算できます。
続いて、各ノードについて、全ノード数の半分以下（全子ノード数と
v - currentNodeSize を合わせた親側の部分木のサイズも含む）であるかどうかを調べてみましょう。Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB