TopCoder SRM 686 (Div. 2) Easy. TreeAndVertex
問題概要
木が与えられる。頂点をひとつ削除したとき出来る連結成分は最大でいくつだろうか。
解法
下図の木を考えてみる。頂点 0 を削除してみよう。
すると 5 つの連結成分が現れる。5 という値は 0 から出ている辺の数に由来している。
よって、各頂点から出ている辺の数を数えて、その最大値を求めればいい。
TopCoder SRM 686 (Div. 2) Easy. TreeAndVertex
tree[i] は i の親ではなく i+1 の親であるということに注意。