严神又准备开一家商店, 这次他突然发现, 街道变成了一个奇怪的结构。
这次的居民都住在 n 个居民点上,每个居民点都有一个居民。 居民点之间用 n - 1 条双向道路连接。 每个居民的不悦指数定义为该居民到商店所需经过的最少道路数。 多个居民的不悦指数等于这些居民的不悦指数之和。
严神想知道, 如果他在这里开一家商店, 居民们的不悦指数最少是多少。
输入共 n 行。
第 1 行, 一个整数 n , 代表居民点的数量。
接下来 n - 1 行, 每行 2 个整数 x , y . 代表居民点 x 和 y 有一条双向道路联通。
我们保证每两个居民点均可以通过道路直接或间接联通。
输出仅一个整数, 最小的不悦指数。
8 1 2 1 3 1 4 3 5 3 6 4 7 7 8
12
严神可以把商店开在居民点 1, 所有居民点的不悦指数为0, 1, 1, 1, 2, 2, 2, 3.其和为12. 可以证明, 没有其他方法能使得不悦指数少于12.
对于 30% 的数据, n \leq 5 \cdot 10^3 ;
对于 100% 的数据, 1 \leq n \leq 5 \cdot 10^4, x \neq y , .