机器选择(Machine Selection)

题目描述

小 Z 所在的机房有 $n$ 台机器，且有局域网，所有机器通过一些网线连接起来，其整个布局是一个树形结构，即任意两台机器间都有且仅有一条路径。小 Z 想在其中某一台机器上储存这个文件，需要的同学就可以直接通过局域网来下载这个文件。

网络上信息传输是需要时间的，我们定义两台机器间数据传输的时间为连接这两台机器的路径所包含的网线数量。虽然机房里通过局域网传个文件是很快的，但对于急不可耐的同学们来说，一分一秒都是宝贵的，文件传输越快越好。所以小 Z 要选择一台机器存储文件，使得所有机器下载这个文件需要的总时间（即最后一台机器完成下载的时间）尽可能短。

现在，你需要给出这个最短时间，以便让小 Z 看看他的决策是否最优。

输入格式

第一行有一个正整数 $n$，机房中机器的数量。

第 $2\sim n$ 行，每行两个整数 $u_i,v_i$ 表示 $u_i,v_i$ 之间有一条网线连接。机器编号为 $1-n$。

输出格式

一行一个整数，表示最短时间。

样例输入 #1

5
3 2
2 1
5 2
2 4

样例输出 #1

1

数据范围

对于 $30\%$ 的数据，$n\le 100$。

对于 $40\%$ 的数据，$n\le 1000$。

对于 $100\%$ 的数据，$2\le n \le 10^5,1\le u_i,v_i \le n$，并且保证输入数据构成一棵树。

知识点与难度

本题涉及的知识点从属于 CSP-S，难度（CF Rating）：1300。

测试点分布

出处：原题链接