4051: 树大剖解
Time Limit: 15.000 Sec Memory Limit: 1024 MBSubmit: 17 Solved: 4
[Submit] [Status] [Web Board] [Creator:]
Description
有一棵有 n 个点的树，树中有一个关键点 1，你需要通过连边使得每一个点与关键点距离 ≤3，问连边数最少是多少。
Input
第一行一个整数 n ，代表树有 n 个点
接下来 n−1 行，每行 2 个整数 x, y ，代表树上有无向边 (x, y)
Output
一行一个整数 ans，表示至少要连 ans 条边
Sample Input
10
3 10
10 6
3 8
8 1
1 9
3 2
9 7
8 4
4 5Sample Output
1
HINT
连接边 (1, 3)
