CF1930H Interactive Mex Tree

这是一个交互题。 Alice 有一棵包含 $n$ 个节点的树 $T$，节点编号为 $1$ 到 $n$。Alice 会把 $T$ 展示给 Bob。Bob 观察 $T$ 后，需要告诉 Alice 两个 $[1,2,\ldots,n]$ 的排列 $p_1$ 和 $p_2$。 然后，Alice 会进行 $q$ 轮如下的游戏。 - Alice 会创建一个数组 $a$，它是 $[0,1,\ldots,n-1]$ 的一个排列。节点 $v$ 的值为 $a_v$。 - Alice 会选择树 $T$ 上的两个节点 $u$ 和 $v$（$1 \leq u, v \leq n$，$u \neq v$），并告知 Bob。Bob 需要找出从节点 $u$ 到 $v$ 的唯一简单路径上所有节点的值的 $\operatorname{MEX}^\dagger$。 - 为了找到这个值，Bob 每轮最多可以向 Alice 询问 $5$ 次。每次询问，Bob 需要给出三个整数 $t$、$l$ 和 $r$，其中 $t$ 只能取 $1$ 或 $2$，且 $1 \leq l \leq r \leq n$。Alice 会返回 $$ \min_{i=l}^{r} a[p_{t,i}] $$ 的值。 注意所有轮次互相独立。特别地，不同轮次的 $a$、$u$ 和 $v$ 可以不同。 Bob 很困惑，因为他只会用 HLD（重链剖分）来做，每轮需要 $O(\log n)$ 次询问。所以他需要你的帮助来赢得游戏。 $^\dagger$ $\operatorname{MEX}$（最小未出现数）定义为：对于一组整数 $c_1, c_2, \ldots, c_k$，$\operatorname{MEX}$ 是不在该集合中出现的最小非负整数 $x$。

每个测试点包含多组测试数据。第一行包含一个整数 $t$（$1 \leq t \leq 10^4$）——表示测试数据组数。请读入它。 每组测试数据的描述如下。 每组测试数据的第一行包含两个正整数 $n$ 和 $q$（$2 \leq n \leq 10^5$，$1 \leq q \leq 10^4$）——表示树 $T$ 的节点数和游戏轮数。 接下来的 $n-1$ 行，每行包含两个整数 $u$ 和 $v$（$1 \leq u, v \leq n$，$u \neq v$），表示树 $T$ 中的一条边。保证给定的边构成一棵树。 保证所有测试数据中 $n$ 和 $q$ 的总和不超过 $10^5$ 和 $10^4$。 还保证所有测试数据中 $n \cdot q$ 的总和不超过 $3 \times 10^6$。 每组测试数据的交互从你输出两个 $[1,2,\ldots,n]$ 的排列 $p_1$ 和 $p_2$ 开始。 新的一行输出 $n$ 个两两不同的整数，表示 $p_1$。 下一行输出 $n$ 个两两不同的整数，表示 $p_2$。 Alice 会开始进行游戏。 每轮，你需要读入两个整数 $u$ 和 $v$（$1 \leq u, v \leq n$，$u \neq v$）。你需要找出从 $u$ 到 $v$ 的唯一简单路径上所有节点的值的 $\operatorname{MEX}$。 为了进行一次询问，输出 "? $t$ $l$ $r$"（不含引号），其中 $t$ 只能取 $1$ 或 $2$，$1 \leq l \leq r \leq n$。随后你需要读入一个整数——表示本次询问的答案 $\min_{i=l}^{r} a_{p_{t,i}}$。每轮最多只能进行 $5$ 次询问。 如果你想输出答案，输出 "! $x$"（$1 \leq x, y \leq n$，不含引号）。之后读入一个整数，通常为 $1$。 如果你收到 $-1$ 而不是有效回复，说明你的程序进行了非法询问、超出询问次数限制，或在上一组测试数据中给出了错误答案。你的程序必须立即终止，否则会收到 Wrong Answer 判定。否则，你的程序会继续从已关闭的流中读取，可能得到任意判定。 每次输出询问或答案后，不要忘记输出换行并刷新输出缓冲区。否则会收到 Idleness limit exceeded 判定。具体做法如下： - C++：fflush(stdout) 或 cout.flush() - Java：System.out.flush() - Pascal：flush(output) - Python：stdout.flush() - 其它语言请查阅相关文档。

见上文交互说明。

在第一个测试点中，交互过程如下： 有 1 组测试数据。 3 1 树 $T$ 有 $3$ 个节点，Alice 只玩一轮。 1 2 第一条边 2 3 第二条边 1 2 3 排列 $p_1$ 2 1 3 排列 $p_2$ Alice 在唯一一轮前将 $a$ 洗牌为 $a=[0,2,1]$。 2 3 本轮询问的节点 ? 1 2 3 $\min(a_{p_{1,2}},a_{p_{1,3}})=\min(a_2,a_3)=1$ ? 2 1 3 $\min(a_{p_{2,1}},a_{p_{2,2}},a_{p_{2,3}})=\min(a_2,a_1,a_3)=0$ ! 0 1 结合询问的输出可知，$\operatorname{MEX}$ 为 $0$。由于输出正确，评测返回 $1$。 每组测试数据结束后，记得读入 $1$ 或 $-1$。 由 ChatGPT 4.1 翻译