P6142 [USACO20FEB] Delegation P
题目描述
Farmer John 有 $N$ 个牧场,这些牧场通过 $N-1$ 条道路连接,形成了一个树形结构。
但在 28 年的经营后(译者注:USACO 创办于 1992 年),FJ 觉得处理树上问题非常辣手,他认为一条链上的问题更加简单。
因此他决定将整棵树划分为若干条链,将每一条链的管理权授予一位工人。他不关心链的数量,却关心链的长度,他希望划分的链都尽可能长,从而不会有人用效率低下的算法蒙混过关。
FJ 现在想知道最大的正整数 $K$,使得整棵树被划分成若干条链,且每条链的长度都**至少**是 $K$。
输入格式
无
输出格式
无
说明/提示
### 样例解释
一种划分方案如下:
$$
2-1-6-7-8, 3-1-4-5
$$
### 子任务
- 测试点 $2 \sim 4$ 满足**最多**有一个点的度数大于 $2$。
- 测试点 $5 \sim 8$ 满足 $N \leq 10^3$。
- 测试点 $9 \sim 15$ 没有特殊限制。