Delegation

题目描述

农夫约翰的农场由 $N$ 个牧场组成（$2 \leq N \leq 10^5$），它们通过 $N-1$ 条道路连接，使得从任意一个牧场都可以到达任意另一个牧场。也就是说，这个农场是一棵树。

但是，在处理了 28 年树上不可避免出现的棘手算法问题之后，FJ 认为树形结构的农场实在太复杂了。他相信在路径上算法问题会更简单。

因此，他计划将道路集合划分为若干条路径，并把这些路径的责任分配给他那些值得信赖的农场工人。他不在乎路径的数量。然而，他希望这些路径都尽可能长，这样任何工人都无法用渐进意义上低效的算法蒙混过关！

请帮助农夫约翰确定最大的正整数 $K$，使得这些道路可以被划分为若干条长度至少为 $K$ 的路径。

输入格式

第一行包含一个整数 $N$。 接下来的 $N-1$ 行，每行包含两个用空格分隔的整数 $a$ 和 $b$，表示顶点 $a$ 与顶点 $b$ 之间的一条边。$a$ 和 $b$ 均在范围 $1 \ldots N$ 内。

输出格式

输出 $K$。

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

3

提示

评分： 在测试点 2-4 中，树构成一颗星形；至多只有一个顶点的度数大于 2。 测试点 5-8 满足 $N\le 10^3$。 测试点 9-15 没有额外限制。

一种可能的路径集合如下：

题目作者：Mark Gordon 和 Dhruv Rohatgi

标签: USACO|2020|Platinum

来源

USACO|2020|Platinum