Treasure Hunt
Time limit2sMemory limit128 MB
Given a tree of rooms, compute the minimum worst-case number of queries needed to locate a hidden treasure using an optimal centroid-based questioning strategy.
- Level
Medium7 of 10
- Topics
- Tree, Divide and conquer, DFS, Greedy
- Solved
- No attempts yet
Problem
There is a maze with n rooms. Between any two rooms, exactly one path exists.
A treasure is hidden in one room. On each question, the searcher chooses one room. If the treasure is in that room, the answer says so. Otherwise, the answer identifies which corridor adjacent to the chosen room must be followed to move toward the treasure.
Given the maze, assume the searcher always chooses questions optimally. Find the minimum number of questions needed to determine the treasure's location in the worst case.
Input
The first line contains the number of rooms n. (1 ≤ n ≤ 50,000)
Each of the next n - 1 lines contains two integers a and b, meaning that rooms a and b are connected by a corridor. Rooms are numbered consecutively from 1 to n.
Output
Print the number of questions needed in the worst case, assuming an optimal strategy.
Hint
For the visible test's structure, asking first about room 1, 2, or 3 lets the searcher determine the treasure's location in at most two questions. Asking first about room 4 or 5 makes three questions necessary in the worst case.