#P2237. [NCPC2009]Flight Planning

    ID: 1262 传统题 1000ms 256MiB 尝试: 84 已通过: 29 难度: 5 上传者: 标签>CF1700普及+/提高-暴力枚举两次遍历求直径广度优先搜索

[NCPC2009]Flight Planning

题目描述

S航空公司在 NN 座城市之间有 N−1N-1 条航线,航线是双向的。任意两座城市都是可以互相到达的,但是可能需要在一些城市换乘不同的航线。 目前有人抱怨要到达有些城市需要换乘太多次,S航空公司为了缓解这一现状,决定取消目前的一条航线,添加另一条航线,在保证任意两座城市还是可以互相到达的前提下,使得两座城市之间需要乘坐的航线次数的最大值最小。

输入格式

第一行为一个整数 N(4≤N≤2500)N(4\le N \le 2500),表示城市的个数。城市从 11 到 NN 编号。 接下来N-1行,每行是一对整数 aa 和 bb,表示一条连接 aa 和 bb 的航线(1≤a,b≤n1\le a,b\le n)。

输出格式

输出仅一行,即航空公司进行调整后,任意两座城市之间需要乘坐的航班次数的最大值。

4
1 2
2 3
3 4
2

【样例解释】

取消3-4的航线,添加2-4的航线。

提示

对于 100%100\% 的数据,N≤2500N\le2500。

题目来源

没有写明来源