/ Randle / 题库 /

树T1

树T1

【问题描述】
树由n 个点,n-1 条边组成,结点编号为1到n。树上任意两个点
之间路径唯一。
定义某个点到某条路径的距离为:该点到路径上最近的一个点需要经过
的边的数量。
现在想知道怎样选两个点确定一条路径,使得距离这个路径最远的点尽
量近。要求你输出距离路径最远的点距离路径的距离。
【输入格式】
第一行一个整数n。其中1<=n<=100,000
接下来n-1行,每行两个整数u 和v,表示结点u 和结点v 之间有
⼀条边。
【输出格式】
一行一个整数,为题目要求的答案。
【样例输入】
8
1 2
2 3
1 4
4 5
1 6
6 7
7 8
4
【样例输出】
2
【样例解释】
可以选择3 到7 作为一条链,那么此时距离这条链最远的点是5,距离
为2。可以发现不存在其他的⼀条链,使得最远点的距离更短。
【数据规模和约定】
对于10% 的数据,保证n = 99998,且树退化成一条链。
对于另外30% 的数据,保证n = 100。
对于另外30% 的数据,保证n = 99999,且最终答案小于等于5。
对于剩余的30% 的数据,保证n = 100000。

信息

难度
9
分类
(无)
标签
(无)
递交数
9
已通过
1
通过率
11%
上传者