TopCoder SRM 686 (Div. 2) Easy. TreeAndVertex

問題概要

木が与えられる。頂点をひとつ削除したとき出来る連結成分は最大でいくつだろうか。

解法

下図の木を考えてみる。頂点 0 を削除してみよう。

f:id:pekempey:20160329165356p:plain:w400

すると 5 つの連結成分が現れる。5 という値は 0 から出ている辺の数に由来している。

よって、各頂点から出ている辺の数を数えて、その最大値を求めればいい。

TopCoder SRM 686 (Div. 2) Easy. TreeAndVertex

tree[i] は i の親ではなく i+1 の親であるということに注意。