CF1453E Dog Snacks

Gildong 正在和他的狗 Badugi 玩耍。他们在一个有 $n$ 个路口的公园里，公园有 $n-1$ 条双向道路，每条道路长度为 $1$ 米，连接着两个路口。路口编号从 $1$ 到 $n$，对于每一对 $a$ 和 $b$（$1 \le a, b \le n$），都可以通过某些道路从第 $a$ 个路口到达第 $b$ 个路口。 Gildong 在公园的每个路口都放了一个零食。现在 Gildong 要给 Badugi 一个任务，让它吃掉所有的零食。Badugi 从第 $1$ 个路口出发，并按照以下规则移动： - Badugi 会寻找离自己最近的零食。这里的距离指的是 Badugi 当前所在位置到有零食的路口的最短路径长度。然而，Badugi 的嗅觉只能感知到距离自己不超过 $k$ 米的零食。如果它找不到这样的零食，则任务失败。 - 在所有 Badugi 能闻到的零食中，它会选择距离自己最近的一个。如果有多个距离相同的零食，Badugi 会任意选择其中一个。 - Badugi 重复这个过程，直到吃掉所有 $n$ 个零食。之后，它还需要回到第 $1$ 个路口，并且从最后一个吃掉零食的路口到第 $1$ 个路口的距离也不能超过 $k$ 米。如果能做到，任务完成；否则，任务失败。 不幸的是，Gildong 并不知道 $k$ 的值。因此，他希望你帮他找出使 Badugi 能完成任务的最小 $k$ 值（假设 Badugi 总是以最优方式移动）。

每组测试包含一个或多个测试用例。第一行包含一个整数 $t$（$1 \le t \le 10^4$），表示测试用例的数量。 每个测试用例的第一行包含一个整数 $n$（$2 \le n \le 2 \cdot 10^5$），表示公园的路口数量。 接下来的 $n-1$ 行，每行包含两个整数 $u$ 和 $v$（$1 \le u, v \le n$，$u \ne v$），表示有一条道路连接着路口 $u$ 和 $v$。所有道路都是双向且互不相同。 保证： - 对于每个测试用例，对于任意 $a$ 和 $b$（$1 \le a, b \le n$），都可以从 $a$ 号路口到达 $b$ 号路口。 - 所有测试用例中 $n$ 的总和不超过 $2 \cdot 10^5$。

对于每个测试用例，输出一个整数，表示使 Badugi 能完成任务的最小 $k$ 值。

在第一个样例中，Badugi 可以用 $k=2$ 完成任务，移动过程如下： 1. Badugi 最初在第 $1$ 个路口，最近的零食就在这里，直接吃掉。 2. 接下来，他寻找最近的零食，可以选择第 $2$ 个或第 $3$ 个路口的零食。假设他选择第 $2$ 个路口，移动 $1$ 米并吃掉零食。 3. 现在只剩下第 $3$ 个路口的零食，需要经过 $2$ 条路才能到达。 4. 吃掉第 $3$ 个路口的零食后，需要回到第 $1$ 个路口，距离为 $1$ 米，完成任务。 在第二个样例中，唯一的移动顺序是 $1$ – $2$ – $3$ – $4$ – $1$。由于第 $4$ 个路口到第 $1$ 个路口的距离为 $3$，所以 $k$ 至少为 $3$。 在第三个样例中，Badugi 可以按如下顺序移动：$1$ – $5$ – $6$ – $7$ – $8$ – $2$ – $3$ – $4$ – $1$。可以证明，只有 $k=3$ 时 Badugi 才能完成任务。  由 ChatGPT 4.1 翻译