

Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 450 点
問題文
「ユ木」を、以下の手順で生成することができる木と定義します。
- 正整数 x,y を選ぶ
- 頂点を 1 つ用意する
- 別に x 個の頂点を用意し、それぞれを手順 2 で用意した頂点と辺で結ぶ
- 手順 3 で用意した x 個の頂点それぞれに、 y 個の葉をつける
x=4,y=2 のユ木を下図に示します。手順 2,3,4 で用意される頂点をそれぞれ赤、青、緑で示しています。
N 頂点の木 T が与えられます。頂点には 1 から N の番号が付けられており、 i\;(=1,2,\dots,N-1) 番目の辺は頂点 u_i と頂点 v_i を結びます。
T の 0 個以上の頂点とそれに隣接する辺を削除して 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:
- Choose positive integers x,y.
- Prepare one vertex.
- Prepare x more vertices, and connect each of them to the vertex prepared in step 2.
- 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