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 \lt 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.

这是一个交互式问题。

在本交互式问题中，你将得到一个由 $n$ 个顶点构成的无环、连通、无向图。我们定义两个顶点 $v$ 和 $u$ 之间的一条路径为一个由互不相同的顶点组成的序列 $p_1, p_2,\dots p_k$，满足 $p_1 = v$，$p_k = u$，且对所有 $i$（$1 \le i < k$），顶点 $p_i$ 与 $p_{i+1}$ 之间存在一条边。

存在两个隐藏顶点 $x$ 和 $y$（它们可能重合）。你可以进行如下查询：

• 选择两个顶点 $a$、$b$（$1\le a, b\le n$）。评测系统将返回 $1$，当且仅当顶点 $x$ 与 $y$ 之间的路径和顶点 $a$ 与 $b$ 之间的路径至少有一个公共顶点；否则返回 $0$。

你的任务是在至多 $\lfloor\frac{n}{2}\rfloor + 1$ 次查询内，找出 $x$ 与 $y$ 之间路径上的至少一个顶点。

注意：该交互器是自适应的，这意味着隐藏顶点可能根据你的查询而改变，但其变化不会与之前的所有查询结果产生矛盾。

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$.

每个测试包含若干个测试用例。第一行包含一个整数 $t$（$1\le t\le 10^4$），表示测试用例的数量。接下来的行描述各个测试用例。

每个测试用例的第一行包含一个整数 $n$（$2\le n\le 2\cdot 10^5$），表示图中顶点的数量。

随后是 $n - 1$ 行，每行包含两个整数 $v$ 和 $u$（$1\le v, u\le n$），表示顶点 $v$ 和 $u$ 在图中由一条边相连。

保证所有测试用例的 $n$ 值之和不超过 $2\cdot 10^5$。