CF2193G Paths in a Tree

This is an interactive problem. In this interactive problem, you are given an acyclic, connected, undirected graph consisting of $ n $ vertices. We define a path between two vertices $ v $ and $ u $ as a sequence of distinct vertices $ p_1, p_2,\dots p_k $ such that $ p_1 = v $ , $ p_k = u $ , and for all $ i $ ( $ 1 \le i < k $ ), there exists an edge between vertices $ p_i $ and $ p_{i+1} $ . There are hidden vertices $ x $ and $ y $ (they may coincide). You can make the following queries: - Choose two vertices $ a $ , $ b $ ( $ 1\le a, b\le n $ ). The jury will respond with $ 1 $ if the path between vertices $ x $ , $ y $ and the path between vertices $ a $ , $ b $ share at least one common vertex, and will respond with $ 0 $ otherwise. Your task is to find at least one vertex on the path between $ x $ and $ y $ in no more than $ \lfloor\frac{n}{2}\rfloor + 1 $ queries.Note that the interactor is adaptive, which means that the hidden vertices may change depending on your queries, but will not contradict previous queries.

Each test consists of several test cases. The first line contains one integer $ t $ ( $ 1\le t\le 10^4 $ ) — the number of test cases. The following lines describe the test cases. The first line of each test case contains one integer $ n $ ( $ 2\le n\le 2\cdot 10^5 $ ) — the number of vertices in the graph. Next, there are $ n - 1 $ lines, each containing two integers $ v $ , $ u $ ( $ 1\le v, u\le n $ ), indicating that vertices $ v $ and $ u $ are connected by an edge in the graph. It is guaranteed that the sum of $ n $ across all test cases does not exceed $ 2\cdot 10^5 $ .

N/A