A7172 | $雾港城的服务中心$

时间限制1s

内存限制128MB

通过 / 提交0/0

题目描述

雾港城要在路网中建立两座服务中心。城市路网是一棵树：有 $n$ 个路口（编号 $1..n$）与 $n-1$ 条双向道路。 你需要选择两个路口作为中心。对任意路口 $x$，它到最近中心的距离定义为： $$ \operatorname{dist}(x)=\min\bigl(d(x,A),\ d(x,B)\bigr), $$ 其中 $A,B$ 为选定的两个中心，$d(u,v)$ 表示点 $u$ 到点 $v$ 的最短路长度（按边数计）。 城市的“最慢响应距离”定义为 $$ \max_{x\in{1,2,\dots,n}} \operatorname{dist}(x). $$ 你的任务是使上述值尽可能小，并输出其最小可能值。

第一行一个整数 $n$。 接下来 $n-1$ 行，每行两个整数 $u,v$，表示一条连接 $u$ 与 $v$ 的无向边。

输出一个整数，表示最小可能的 $$ \max_{x} \operatorname{dist}(x). $$

输入 #1

输出 #1

C++ 编辑器

输入

输出