题目描述

在公司机房中，有 $n$ 台交换机以树形结构连接，交换机的编号从 $1$ 到 $n$。管理员希望选择一台交换机作为公网接入点（即树的根节点），使得这台交换机到其他任意交换机的最大跳数最小。请计算并输出这个最小的最大跳数。

思路

在树形结构中，最远的两点之间的路径长度称为树的直径。为了使根节点到其他所有节点的最大跳数最小，应将根节点放在直径的中间位置（即树的中心）。这样，根节点到最远节点的距离就是直径的一半，可能为整数或半整数。由于跳数必须是整数，所以我们取整数部分再加一，即最小的最大跳数为 (直径 + 1) / 2。因此，把边权设置为1，树形dp或者dfs,bfs求树的直径，答案为(树的直径+1)/2，这里提供bfs解法

cpp

#include <iostream>

题目内容

公司机房内由多台交换机树状组网，当前管理员想从这些交换机中选择一台起点交换机作为公网接入点，要求起点交换机到其他交换机最大跳数最小，请输出这个跳数最小值。

例如，当下面第一张图选取 $3$ 号交换机作为起点交换机时，$3$ 号交换机到 $1$ 号和 $4$ 号交换机跳数为 $1$ ，到 $2$ 号、 $5$ 号和 $6$ 号交换机跳数为 $2$ ，则跳数最小值为 $2$ 。

输入描述

第一行一个正整数 $n(1 ≤n ≤ 10^5)$，表示 $n$ 个交换机的编号从 $1$ 到 $n$ 。

接下来 $n-1$ 行每行两个正整数 ,$x,y(1≤x,y≤n)$,表示有一 条连接 $x,y$ 的边。

输出描述

一个正整数表示跳数最小值。

样例1

输入

7
1 2
1 3
3 4
4 5
4 6
4 7

输出

2

说明

请参考题目描述第一张图， $3$ 号交换机作为树的根节点后，树的深度为 $2$ 。

样例2

输入

8
1 2
1 3
3 4
3 5
5 6
5 7
7 8

输出

3

说明

请参考题目描述第二张图，选择 $3$ 号或 $5$ 号交换机作为树的根节点后，树的深度为 $3$ 。