Interactive Mex Tree_信奥算法NOI/NOI+/CTSC-ACGO题库

题目描述

This is an interactive problem.

Alice has a tree $T$ consisting of $n$ nodes, numbered from $1$ to $n$ . Alice will show $T$ to Bob. After observing $T$ , Bob needs to tell Alice two permutations $p_1$ and $p_2$ of $[1, 2, \ldots, n]$ .

Then, Alice will play $q$ rounds of the following game.

Alice will create an array $a$ that is a permutation of $[0,1,\ldots,n-1]$ . The value of node $v$ will be $a_v$ .
Alice will choose two nodes $u$ and $v$ ( $1 \leq u, v \leq n$ , $u \neq v$ ) of $T$ and tell them to Bob. Bob will need to find the $\operatorname{MEX}^\dagger$ of the values on the unique simple path between nodes $u$ and $v$ .
To find this value, Bob can ask Alice at most $5$ queries. In each query, Bob should give three integers $t$ , $l$ and $r$ to Alice such that $t$ is either $1$ or $2$ , and $1 \leq l \leq r \leq n$ . Alice will then tell Bob the value equal to $$\min_{i=l}^{r} a[p_{t,i}].$$

Note that all rounds are independent of each other. In particular, the values of $a$ , $u$ and $v$ can be different in different rounds.

Bob is puzzled as he only knows the HLD solution, which requires $O(\log(n))$ queries per round. So he needs your help to win the game.

$^\dagger$ The $\operatorname{MEX}$ (minimum excludant) of a collection of integers $c_1, c_2, \ldots, c_k$ is defined as the smallest non-negative integer $x$ which does not occur in the collection $c$ .

Interaction

Each test contains multiple test cases. The first line contains a single integer $t$ ( $1 \leq t \leq 10^4$ ) — the number of test cases. Read it. The description of the test cases follows.

The first line of each test case contains two positive integers $n$ and $q$ ( $2 \leq n \leq 10^5$ , $1 \leq q \leq 10^4$ ) — the number of nodes in $T$ and the number of rounds respectively.

The following next $n-1$ lines contains two integers $u$ and $v$ ( $1 \leq u, v \leq n$ , $u \neq v$ ) — denoting an edge between nodes $u$ and $v$ . It is guaranteed that the given edges form a tree.

It is guaranteed that the sum of $n$ and $q$ over all test cases does not exceed $10^5$ and $10^4$ respectively.

It is also guaranteed that the sum of $n \cdot q$ does not exceed $3 \cdot 10^6$ .

The interaction for each test case begins by outputting two permutations $p_1$ and $p_2$ of $[1, 2, \ldots, n]$ .

On a new line, output $n$ space-separated distinct integers denoting $p_1$ .

In the next line, output $n$ space-separated distinct integers denoting $p_2$ .

Alice will start playing the game.

For each round, you must read two integers, $u$ and $v$ ( $1 \leq u, v \leq n$ , $u \neq v$ ). You need to find the $\operatorname{MEX}$ of the values on the unique simple path between nodes $u$ and $v$ .

To make a query, output "? $t$ $l$ $r$ " without quotes, such that $t$ is either $1$ or $2$ , and $1 \leq l \leq r \leq n$ . Afterwards, you should read a single integer — the answer to your query $\min_{i=l}^{r} a_{p_{t,i}}$ . You can make at most $5$ such queries in each round.

If you want to print the answer, output "! $x$ " ( $1 \leq x, y \leq n$ ) without quotes. After doing that, read a single integer, which is normally equal to $1$ .

If you receive the integer $-1$ instead of a valid reply, it means your program has made an invalid query, exceeded the query limit, or gave an incorrect answer on the previous test case. Your program must terminate immediately to receive a Wrong Answer verdict. Otherwise, you can get an arbitrary verdict because your solution will continue to read from a closed stream.

After printing a query or the answer, do not forget to output the end of the line and flush the output. Otherwise, you will get Idleness limit exceeded. To do this, use:

fflush(stdout) or cout.flush() in C++;
System.out.flush() in Java;
flush(output) in Pascal;
stdout.flush() in Python;
see documentation for other languages.

Hacks

To hack, follow the test format below.

The first line should contain a single integer $t$ ( $1 \le t \le 10^4$ ) — the number of test cases.

The first line of each test case should contain two positive integers $n$ and $q$ ( $2 \leq n \leq 10^5$ ; $1 \leq q \leq 10^4$ ) — the number of nodes in $T$ and the number of rounds respectively.

The following next $n-1$ lines should contain two integers $u$ and $v$ ( $1 \leq u, v \leq n$ , $u \neq v$ ) — denoting an edge between nodes $u$ and $v$ . The given edges must form a tree.

For each of the $q$ rounds, first print a permutation of $[0, 1, 2, \ldots, n-1]$ on a new line, denoting the array $a$ chosen by Alice during the start of the round.

In the following line, print two distinct nodes $u$ and $v$ ( $1 \leq u, v \leq v$ , $u \neq v$ ), representing the endpoints of the path asked by Alice.

The sum of $n$ and $q$ over all test cases should not exceed $10^5$ and $10^4$ respectively.

The sum of $n \cdot q$ should not exceed $3 \cdot 10^6$ .

这是一个交互式问题。

爱丽丝有一棵包含 $n$ 个节点的树 $T$ ，节点编号为 $1$ 到 $n$ 。爱丽丝会将 $T$ 展示给鲍勃。在观察完 $T$ 后，鲍勃需要告诉爱丽丝两个排列 $p_1$ 和 $p_2$ ，它们均为 $[1, 2, \ldots, n]$ 的排列。

随后，爱丽丝将进行 $q$ 轮如下游戏：

爱丽丝将构造一个数组 $a$ ，它是 $[0,1,\ldots,n-1]$ 的一个排列；节点 $v$ 的值即为 $a_v$ 。
爱丽丝将在 $T$ 中选择两个节点 $u$ 和 $v$ （满足 $1 \leq u, v \leq n$ 且 $u \neq v$ ），并将它们告知鲍勃。鲍勃需要求出节点 $u$ 与 $v$ 之间唯一简单路径上所有节点取值的 $\operatorname{MEX}^\dagger$ 。
为求得该值，鲍勃每轮最多可向爱丽丝提出 $5$ 次询问。每次询问中，鲍勃需向爱丽丝提供三个整数 $t$ 、 $l$ 和 $r$ ，其中 $t$ 只能是 $1$ 或 $2$ ，且满足 $1 \leq l \leq r \leq n$ 。爱丽丝将返回以下值：

$\min_{i=l}^{r} a[p_{t,i}].$

注意：所有轮次相互独立。特别地，不同轮次中数组 $a$ 、节点 $u$ 和 $v$ 的取值均可不同。

鲍勃感到困惑，因为他只知道基于重链剖分（HLD）的解法，而该解法每轮需 $O(\log(n))$ 次询问。因此他需要你的帮助来赢得这场游戏。

$^\dagger$ 一组整数 $c_1, c_2, \ldots, c_k$ 的 $\operatorname{MEX}$ （最小未出现非负整数）定义为未出现在该集合 $c$ 中的最小非负整数 $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$ ），表示节点 $u$ 与 $v$ 之间存在一条边。保证所给边构成一棵树。

保证所有测试用例中 $n$ 的总和不超过 $10^5$ ， $q$ 的总和不超过 $10^4$ 。

同时保证所有测试用例中 $n \cdot q$ 的总和不超过 $3 \cdot 10^6$ 。

每个测试用例的交互以输出两个排列 $p_1$ 和 $p_2$ （均为 $[1, 2, \ldots, n]$ 的排列）开始。

在新的一行中，输出 $n$ 个以空格分隔的互不相同的整数，表示 $p_1$ 。

在下一行中，输出 $n$ 个以空格分隔的互不相同的整数，表示 $p_2$ 。

此后爱丽丝开始进行游戏。

对每一轮，你必须读入两个整数 $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（不含引号）（注意：此处原文有误，应为 ! x，而非 ! x y；且 $x$ 应为非负整数，无 $1 \le x, y \le n$ 的限制）。输出后，请读入一个整数，该整数通常等于 $1$ 。

若你收到的整数为 $-1$ 而非有效回复，则说明你的程序发出了非法询问、超出询问次数限制，或在上一测试用例中给出了错误答案。此时你的程序必须立即终止，以获得“Wrong Answer”判决。否则，由于你的程序将继续从已关闭的流中读取数据，你可能会得到任意判决。

在输出一次询问或答案后，切勿忘记输出换行符并刷新输出缓冲区。否则你会收到 “Idleness limit exceeded”。为此，请使用：

C++ 中：fflush(stdout) 或 cout.flush()；
Java 中：System.out.flush()；
Pascal 中：flush(output)；
Python 中：stdout.flush()；
其他语言请参阅相应文档。

Hack 方法

要 hack 本题，请按如下格式构造测试数据。

第一行应为一个整数 $t$ （ $1 \le t \le 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$ ），表示节点 $u$ 与 $v$ 之间存在一条边。所给边必须构成一棵树。

对 $q$ 轮中的每一轮，首先在新一行输出一个 $[0, 1, 2, \ldots, n-1]$ 的排列，表示爱丽丝在该轮开始时选定的数组 $a$ 。

在下一行中，输出两个互异的节点 $u$ 和 $v$ （ $1 \leq u, v \leq n$ ， $u \neq v$ ），表示爱丽丝所询问路径的两个端点。

所有测试用例中 $n$ 的总和与 $q$ 的总和分别不应超过 $10^5$ 和 $10^4$ 。

所有测试用例中 $n \cdot q$ 的总和不应超过 $3 \cdot 10^6$ 。

输入输出样例

输入#1

输出#1

说明/提示

In the first test, the interaction proceeds as follows.

Solution

Jury

Explanation

1

There are 1 test cases.

3 1

The tree $T$ consists of $3$ nodes, and Alice will play for only one round.

1 2

First edge of $T$

2 3

Second edge of $T$

1 2 3

The permutation $p_1$

2 1 3

The permutation $p_2$

Alice shuffles $a$ to $a=[0,2,1]$ before giving the nodes for the only round.

2 3

Nodes for the round

? 1 2 3

1

$\min(a_{p_{1,2}},a_{p_{1,3}})=\min(a_2,a_3)=1$

? 2 1 3

0

$\min(a_{p_{2,1}},a_{p_{2,2}},a_{p_{2,3}})=\min(a_2,a_1,a_3)=0$

! 0

1

Considering the output of queries, it is clear that $\operatorname{MEX}$ is $0$ . Since the output is correct, the jury responds with $1$ .

After each test case, make sure to read $1$ or $-1$ .

在第一个测试用例中，交互过程如下所示。

解答

裁判

说明

1

共有 1 个测试用例。

3 1

树 $T$ 包含 $3$ 个节点，且 Alice 仅进行一轮游戏。

1 2

树 $T$ 的第一条边

2 3

树 $T$ 的第二条边

1 2 3

排列 $p_1$

2 1 3

排列 $p_2$

Alice 在向该轮提供节点前，将数组 $a$ 置换为 $a=[0,2,1]$ 。

2 3

该轮所用的节点