P12421 【MX-X12-T4】「ALFR Round 5」游戏

原题链接：。

**这是一道交互题。** 有一棵 $n$ 个点的树，树的形态给定，树上有一个隐藏点 $s$，你每次可以给出一个点 $u$，交互库选择将 $s$ 向 $u$ 移动一步（若 $s=u$ 则无事发生），或者返回目前 $u$ 到 $s$ 的距离。交互库会告诉你他选择的操作，如果选择的是操作 $2$ 会告诉你距离。你需要在 $m$ 次询问内求出**目前** $s$ 的位置。 每个测试点中有 $T$ 组测试数据。 交互库不自适应，这意味着询问开始前 $s$ 的位置确定，与你的询问无关。 **【交互方式】** 首先输入一个正整数 $T$ 表示测试数据组数。 接下来 $T$ 组数据，每组数据的第一行输入两个正整数 $n,m$ 分别表示树的点数和询问次数限制，接下来 $n-1$ 行每行两个数 $u,v$ 表示树上存在一条连接 $u,v$ 的边。 接着你需要进行交互，询问格式为 `? u`，其中需要满足 $1 \leq u \leq n$，如果你本组数据的询问次数超过 $m$，交互库输出 `-1`，此时你需要立即结束程序否则之后交互库行为未定义。若询问次数未超过限制，交互库输出 `1` 或者 `2 d`，分别表示交互库选择将 $s$ 向 $u$ 移动一步或者告诉你 $s$ 到 $u$ 目前的距离为 $d$。当你确定 $s$ 目前的位置后，输出 `! u` 表示 $s$ 目前在编号为 $u$ 的节点上。如果你的回答是正确的，交互库输出 `1` 并进入下一组测试数据，否则交互库输出 `0`，你需要立即结束程序否则之后交互库行为未定义。 **你需要在你的每次输出后刷新缓冲区。** 你可以使用如下语句来清空缓冲区： - 对于 C/C++：`fflush(stdout)`； - 对于 C++：`std::cout

无

无

**【样例解释 #1】** 对于样例 $1$，初始有 $s=3$，询问两次点 $2$，第一次交互库返回 $1$，并将 $s$ 向点 $2$ 移动一步，$s=2$，第二次询问交互库返回 $1$，$s=2$，所以 $s$ 不发生变化。此时可以确定 $s=2$，回答 $s=2$ 后，交互库返回 $1$ 表示答案正确。 **【数据范围】** **本题使用捆绑测试。** | 子任务编号 | $T \leq $ | $n \leq $ | $m = $ | 特殊性质 | 分值 | 子任务依赖 | | :-: | :-: | :-: |:-: |:-: | :-: | :-: | | $1$ | $500$ | $10$ | $200$ | 无 |$5$ | 无 | | $2$ | $10$ | $1000$ | $3n$ | 无 | $13$ | $1$ | | $3$ | $10^4$ | $10^5$ | $n-1$ | A | $7$ | 无 | $4$ | $10^4$ | $10^5$ | $n-1$ | B | $10$ | 无 | $5$ | $10^4$ | $10^5$ | $3n$ | C | $14$ | 无 | | $6$ | $10^4$ | $10^5$ | $2n$ | 无 | $21$ | $1,2,5$ | | $7$ | $10^4$ | $10^5$ | $n-1$ | 无 |$30$ | $1,2,3,4,5,6$ | 特殊性质 A：树上每个点度数不大于 $2$。 特殊性质 B：树上只有至多一个点度数大于 $1$。 特殊性质 C：树的生成方式为：对于每个 $2 \leq i \leq n$，等概率随机选取 $[1,i)$ 中的一个整数 $x$，将 $x$ 与 $i$ 连边。 对于所有数据，$1 \leq T \leq 10^4$，$1 \leq \sum n \leq 10^5$，$m\geq n-1$。