#3265. 「USACO 2020.2 Platinum」Delegation

内存限制:256 MiB 时间限制:2000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: ksyx

题目描述

题目译自 USACO 2020 Feburary Contest, Platinum Problem 1. Delegation

Farmer John 的 N 片牧场由 N-1 条道路连接而成,使得任意一片牧场与其他牧场都联通,形成了树状结构。在研究了由这树状结构产生的各种算法问题 28 年后,他还是觉得农场的结构过于复杂,而他相信研究路径的算法问题更为简单。

因此,他的目标是把牧场间的道路分成一条条路径,然后指定这些路径在他贵重的农场工人的使用过程中起些什么作用。他不关心路径的数目,而是想要这些路径越长越好,使得没有农场工人可以用低效率的算法解决问题。

你的任务是帮 Farmer John 找出最大的整数 K 使得每条道路恰好被分入一条路径中,且路径长度至少为 K

译者注:此处最后一段已修改表述以使得更清晰,如有疑问请查阅原题。

输入格式

第一行一个整数 N

接下来 N-1 行每行两个以空格隔开的整数 a,~b ,表示节点 a 和节点 b 之间有一条边。

输出格式

输出 K

样例

样例输入

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

样例输出

3

样例解释

一个可行的划分方案是: 2-1-6-7-8,~3-1-4-5

数据范围与提示

测试点 2\ldots4 满足输入的结构形成了星状结构,即至多有一个节点的度数大于 2。

测试点 5\ldots8 满足 N\le 10^3

测试点 9\ldots15 无特殊限制。

对于 100\% 的数据,有 2\le N \le 10^5