2531: 联络网
内存限制：256 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：6
解决：2
题目描述
由于女交警太多,小 Y 与她们的联络就成了一个问题。他决定构建一个联络网以便联系。
小 Y 不希望网络太复杂,于是他把联络网设计成了一棵树,这样每次需要联络的时候小 Y
只需给任意一个女交警发短信便可以将信息传达给所有的女交警。我们可以认为女交警从接
到短信到群发出去的时间为 1。
在这个联络网用了一段时间后,小 Y 发现了一个问题:当他给某个女交警发短信时,转
达到一些人需要的时间非常长,这样导致耽误了约会。而小 Y 又不愿意浪费短信费,他希望
每次需要联络时只给一个女交警打电话。小 Y 十分苦恼,他决定修改联络网的一条树边(把
这条树边删去,再添加一条边)。他希望使修改后的联络网满足:从给任意一个女交警发短
信开始,到联络到所有女交警的最长时间尽量短。
小 Y 找到了你帮忙,你一定要帮帮他!
输入
包含若干行。
第一行包含一个整数 N,表示有 N 个女交警。
接下来的 N-1 行,每行两个整数 A、B,表示 A 与 B 之间有边相连。
输出
只包含一行,为一个整数,表示修改后联络的最短时间。
样例输入 复制
5
1 2
2 3
3 4
4 5样例输出 复制
3提示
对于 30%的数据满足, n≤50;
对于 100%的数据满足,n≤2500。