题目名称 3368. [USACO20 Feb Platinum]Delegation(Platinum)
输入输出 usaco_Feb_delegs.in/out
难度等级 ★★★
时间限制 2000 ms (2 s)
内存限制 256 MiB
测试数据 15
题目来源 Gravatar数声风笛ovo 于2020-03-01加入
开放分组 全部用户
提交状态
分类标签
分享题解
通过:1, 提交:2, 通过率:50%
Gravatar瑆の時間~無盡輪迴·林蔭 100 1.986 s 19.38 MiB C++
Gravatar程门立雪 6 2.199 s 0.00 MiB C++
本题关联比赛
USACO铂金组&NOIonline模拟赛
USACO铂金组&NOIonline模拟赛
关于 Delegation(Platinum) 的近10条评论(全部评论)
回复 @ShallowDream雨梨 :
道路修建
Gravatar瑆の時間~無盡輪迴·林蔭
2020-03-04 16:29 2楼
为什么感觉和春节十二响差不多?
GravatarShallowDream雨梨
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 组