E - Snowflake Tree Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 450

問題文

ユ木」を、以下の手順で生成することができる木と定義します。

  1. 正整数 x,y を選ぶ
  2. 頂点を 1 つ用意する
  3. 別に x 個の頂点を用意し、それぞれを手順 2 で用意した頂点と辺で結ぶ
  4. 手順 3 で用意した x 個の頂点それぞれに、 y 個の葉をつける

x=4,y=2 のユ木を下図に示します。手順 2,3,4 で用意される頂点をそれぞれ赤、青、緑で示しています。

N 頂点の木 T が与えられます。頂点には 1 から N の番号が付けられており、 i\;(=1,2,\dots,N-1) 番目の辺は頂点 u_i と頂点 v_i を結びます。

T0 個以上の頂点とそれに隣接する辺を削除して 1 つのユ木にするとき、削除する頂点数の最小値を求めてください。なお、本問題の制約下で、T をかならずユ木にすることができます。

制約

  • 3 \leq N \leq 3 \times 10^5
  • 1 \leq u_i < v_i \leq N
  • 与えられるグラフは木である
  • 入力はすべて整数

入力

入力は以下の形式で標準入力から与えられる。

N
u_1 v_1
u_2 v_2
\vdots
u_{N-1} v_{N-1}

出力

答えを出力せよ。


入力例 1

8
1 3
2 3
3 4
4 5
5 6
5 7
4 8

出力例 1

1

頂点 8 を削除することで、与えられた木を x=2,y=2 のユ木にすることができます。


入力例 2

3
1 2
2 3

出力例 2

0

与えられた木はすでに x=1,y=1 のユ木です。


入力例 3

10
1 3
1 2
5 7
6 10
2 8
1 6
8 9
2 7
1 4

出力例 3

3

Score : 450 points

Problem Statement

A "Snowflake Tree" is defined as a tree that can be generated by the following procedure:

  1. Choose positive integers x,y.
  2. Prepare one vertex.
  3. Prepare x more vertices, and connect each of them to the vertex prepared in step 2.
  4. For each of the x vertices prepared in step 3, attach y leaves to it.

The figure below shows a Snowflake Tree with x=4,y=2. The vertices prepared in steps 2, 3, 4 are shown in red, blue, and green, respectively.

You are given a tree T with N vertices. The vertices are numbered 1 to N, and the i-th edge (i=1,2,\dots,N-1) connects vertices u_i and v_i.

Consider deleting zero or more vertices of T and the edges adjacent to them so that the remaining graph becomes a single Snowflake Tree. Find the minimum number of vertices that must be deleted. Under the constraints of this problem, it is always possible to transform T into a Snowflake Tree.

Constraints

  • 3 \leq N \leq 3 \times 10^5
  • 1 \leq u_i < v_i \leq N
  • The given graph is a tree.
  • All input values are integers.

Input

The input is given from Standard Input in the following format:

N
u_1 v_1
u_2 v_2
\vdots
u_{N-1} v_{N-1}

Output

Print the answer.


Sample Input 1

8
1 3
2 3
3 4
4 5
5 6
5 7
4 8

Sample Output 1

1

By deleting vertex 8, the given tree can be transformed into a Snowflake Tree with x=2,y=2.


Sample Input 2

3
1 2
2 3

Sample Output 2

0

The given tree is already a Snowflake Tree with x=1,y=1.


Sample Input 3

10
1 3
1 2
5 7
6 10
2 8
1 6
8 9
2 7
1 4

Sample Output 3

3