ARC038 C.高橋王国の分割統治

問題

木が与えられる。
ある頂点を取り除いてできる連結成分の最大のサイズを各頂点について計算する。
N<=10^5

考え方

木が与えられたらとりあえず適当な頂点を選んで根付き木にして考える。
木DPで、その頂点以下の部分木の頂点数を求める。
これによって子ノード方向の連結成分の個数を求められる。

逆に、親ノード方向の連結成分の頂点数は、「N-{その頂点以下の部分木の頂点数}」になっているので、各頂点について、それらの中の最大値を返す。