| 题目名称 | 3368. [USACO20 Feb Platinum]Delegation(Platinum) |
|---|---|
| 输入输出 | usaco_Feb_delegs.in/out |
| 难度等级 | ★★★ |
| 时间限制 | 2000 ms (2 s) |
| 内存限制 | 256 MiB |
| 测试数据 | 15 |
| 题目来源 |
 数声风笛ovo
于2020-03-01加入 |
| 开放分组 | 全部用户 |
| 提交状态 | |
| 分类标签 | |
| 分享题解 |
| 通过：1， 提交：2， 通过率：50% | ||||
 瑆の時間~無盡輪迴·林蔭 |
100 | 1.986 s | 19.38 MiB | C++ |
 程门立雪 |
6 | 2.199 s | 0.00 MiB | C++ |
| 本题关联比赛 | |||
| USACO铂金组&NOIonline模拟赛 | |||
| USACO铂金组&NOIonline模拟赛 | |||
| 关于 Delegation(Platinum) 的近10条评论(全部评论) | ||||
|---|---|---|---|---|
|
回复 @ShallowDream雨梨 :
道路修建 | ||||
|
为什么感觉和春节十二响差不多？
 ShallowDream雨梨
2020-03-03 11:45
1楼
| ||||
3368. [USACO20 Feb Platinum]Delegation(Platinum)
★★★ 输入文件：usaco_Feb_delegs.in
输出文件：usaco_Feb_delegs.out
简单对比时间限制：2 s 内存限制：256 MiB
【题目描述】
Farmer John 的农场由 $N$ 块草地（$1 \leq N \leq 10^5$）和 $N-1$ 条道路组成，满足每块草地都能从任意其他草地到达。也就是说，这个农场组成一棵树。但在与不可避免地由树而生的麻烦的算法问题打了 28 年交道之后，FJ 终于认为树形的农场太复杂了。他相信在链上的算法问题更简单。
所以，他的计划是将这些道路划分成若干条链，并将每条链交给他值得信任的农场工人之一负责。他不关心链的数量。然而，他希望确保这些链都尽可能长，从而不会有农场工人能够用一个渐近效率低下的算法蒙混过关！
帮助 Farmer John 求出最大正整数 $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-1-6-7-8, 3-1-4-5$$
【提示】
对于$ 20\% $的测试数据(测试点$ 2 \sim 4 $)，树组成了一个 “星形”，即至多一个结点的度大于二。
另有$ 27\% $的测试数据(测试点$ 5 \sim 8 $)，满足$ N\le 10^3 $。
对于$ 100\% $的测试数据，均满足上文所给出的数据规模。
【来源】
USACO 二月公开赛 Platinum 组