308023: CF1453E. Dog Snacks
Memory Limit:512 MB
Time Limit:3 S
Judge Style:Text Compare
Creator:
Submit:0
Solved:0
Description
Dog Snacks
题意翻译
一只狗在一个树形结构的公园( $n$ 个路口 $n-1$ 条无向边)内觅食,要求每个节点都经过一次,最后回到节点 $1$ ,他遵守以下移动规则: - 每次前往距离自己最近的还未经过的节点,但是距离不能超过 $k$ ,也就是说,如果没有距离为 $k$ 以内的未经过的节点,则失败。 - 如果有多个相同距离的最近未经过节点,则任意选择前往。 - 在走完最后一个节点后回到起点 $1$ ,要求回到起点 $1$ 的距离也不超过 $k$ ,否则也失败。 现在要求求出能保证完成任务的最小 $k$ 是多少。 $n\leq 2\times 10^5$题目描述
Gildong is playing with his dog, Badugi. They're at a park that has $ n $ intersections and $ n-1 $ bidirectional roads, each $ 1 $ meter in length and connecting two intersections with each other. The intersections are numbered from $ 1 $ to $ n $ , and for every $ a $ and $ b $ ( $ 1 \le a, b \le n $ ), it is possible to get to the $ b $ -th intersection from the $ a $ -th intersection using some set of roads. Gildong has put one snack at every intersection of the park. Now Gildong will give Badugi a mission to eat all of the snacks. Badugi starts at the $ 1 $ -st intersection, and he will move by the following rules: - Badugi looks for snacks that are as close to him as possible. Here, the distance is the length of the shortest path from Badugi's current location to the intersection with the snack. However, Badugi's sense of smell is limited to $ k $ meters, so he can only find snacks that are less than or equal to $ k $ meters away from himself. If he cannot find any such snack, he fails the mission. - Among all the snacks that Badugi can smell from his current location, he chooses a snack that minimizes the distance he needs to travel from his current intersection. If there are multiple such snacks, Badugi will choose one arbitrarily. - He repeats this process until he eats all $ n $ snacks. After that, he has to find the $ 1 $ -st intersection again which also must be less than or equal to $ k $ meters away from the last snack he just ate. If he manages to find it, he completes the mission. Otherwise, he fails the mission. Unfortunately, Gildong doesn't know the value of $ k $ . So, he wants you to find the minimum value of $ k $ that makes it possible for Badugi to complete his mission, if Badugi moves optimally.输入输出格式
输入格式
Each test contains one or more test cases. The first line contains the number of test cases $ t $ ( $ 1 \le t \le 10^4 $ ). The first line of each test case contains one integer $ n $ ( $ 2 \le n \le 2 \cdot 10^5 $ ) — the number of intersections of the park. The next $ n-1 $ lines contain two integers $ u $ and $ v $ ( $ 1 \le u,v \le n $ , $ u \ne v $ ) each, which means there is a road between intersection $ u $ and $ v $ . All roads are bidirectional and distinct. It is guaranteed that: - For each test case, for every $ a $ and $ b $ ( $ 1 \le a, b \le n $ ), it is possible to get to the $ b $ -th intersection from the $ a $ -th intersection. - The sum of $ n $ in all test cases doesn't exceed $ 2 \cdot 10^5 $ .
输出格式
For each test case, print one integer — the minimum possible value of $ k $ such that Badugi can complete the mission.
输入输出样例
输入样例 #1
3
3
1 2
1 3
4
1 2
2 3
3 4
8
1 2
2 3
3 4
1 5
5 6
6 7
5 8
输出样例 #1
2
3
3