Delete and Delete 2

頂点からなり、頂点 を根とする根付き木があります。頂点 の親は頂点 です。 これからあなたは以下の操作を繰り返します。

• 根以外の頂点が存在するなら、それらのうち一つを選び、以下に示す「吸収」を行う。その後、葉となっている根以外の頂点を全て削除する。
  • 頂点 に対する吸収：頂点 が葉でなければ、「頂点 の子」の子は全て頂点 の子に変更され、元々の頂点 の子は全て削除される。頂点 が葉であれば、頂点 が削除される。

根以外の頂点を全て削除するまでに行う操作の回数の最小値を求めてください。

• 入力はすべて整数

答えを出力し、最後に改行してください。

4
1 2 1

1

7
1 2 3 2 4 2

2

15
1 1 1 3 1 5 4 3 1 4 9 4 5 4

2