题目内容

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

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

题目描述

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

思路

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

cpp

#include <iostream>