会员专享
请先
登录，登录后可使用今日免费解锁；
开通会员后可解锁完整内容。
题目描述
在公司机房中，有 n 台交换机以树形结构连接，交换机的编号从 1 到 n。管理员希望选择一台交换机作为公网接入点（即树的根节点），使得这台交换机到其他任意交换机的最大跳数最小。请计算并输出这个最小的最大跳数。
思路
在树形结构中，最远的两点之间的路径长度称为树的直径。为了使根节点到其他所有节点的最大跳数最小，应将根节点放在直径的中间位置（即树的中心）。这样，根节点到最远节点的距离就是直径的一半，可能为整数或半整数。由于跳数必须是整数，所以我们取整数部分再加一，即最小的最大跳数为 (直径 + 1) / 2。因此，把边权设置为1，树形dp或者dfs,bfs求树的直径，答案为(树的直径+1)/2，这里提供bfs解法
cpp
