#P9043. [2017年备战省选]b
[2017年备战省选]b
题目描述
一个王国的交通网络是一棵树。国王要选择一个到所有节点的距离和最小的节点。若有多个节点都使距离和最小,可以选择其中任意一个。
允许删去原树的一些边,再加入相同数量的边,使得到的图仍然是一棵树。对每个节点 ,求最少要删去多少条原边,才能使 成为可以被国王选中的节点。
输入格式
第一行一个正整数 ,表示节点数。
接下来 行,每行两个正整数 ,表示节点 之间的一条树边。
输出格式
输出 行。第 行一个整数,表示使节点 可以被选中所需删去的最少原边数。
样例 1
10
1 2
1 3
1 4
1 5
1 6
1 7
1 8
1 9
1 10
0
4
4
4
4
4
4
4
4
4
原题的第二组样例见原比赛样例数据文件夹。
数据范围
| 测试点 | |
|---|---|
| 1–2 | 10 |
| 3–8 | 2000 |
| 9–14 | 100000 |
| 15–20 | 1000000 |