311077: CF1930H. Interactive Mex Tree
Description
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$.
InteractionEach 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$.
ExampleInput1 3 1 1 2 2 3 2 3 1 0 1Output
1 2 3 2 1 3 ? 1 2 3 ? 2 1 3 ! 0Note
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$.
Output
这是一个交互式问题。爱丽丝有一棵由n个节点组成的树T，节点编号从1到n。爱丽丝会向鲍勃展示T。观察T后，鲍勃需要告诉爱丽丝两个排列p1和p2，它们都是[1,2,...,n]的排列。
然后，爱丽丝会进行q轮游戏。
1. 爱丽丝会创建一个数组a，它是[0,1,...,n-1]的一个排列。节点v的值是a_v。
2. 爱丽丝会从T中选出两个节点u和v（1≤u,v≤n，u≠v）并告诉鲍勃。鲍勃需要找到节点u和v之间唯一简单路径上的值的MEX（最小排除数）。
3. 为了找到这个值，鲍勃可以向爱丽丝提出最多5个查询。在每次查询中，鲍勃应该给出三个整数t、l和r给爱丽丝，使得t是1或2，1≤l≤r≤n。爱丽丝会告诉鲍勃等于min_{i=l}^{r} a[p_{t,i}]的值。
注意，所有轮次都是相互独立的。特别是，a、u和v在不同轮次中可以不同。
鲍勃只知道HLD（重链剖分）解决方案，它需要每轮O(log(n))次查询。所以他需要你的帮助来赢得游戏。
输入输出数据格式：
每个测试包含多个测试案例。第一行包含一个整数t（1≤t≤10^4）——测试案例的数量。读取它。测试案例的描述接着这个数字。
每个测试案例的第一行包含两个正整数n和q（2≤n≤10^5，1≤q≤10^4）——树T的节点数和轮数。
接下来的n-1行每行包含两个整数u和v（1≤u,v≤n，u≠v）——表示节点u和v之间的一条边。保证给定的边构成一棵树。
每个测试案例以输出两个排列p1和p2开始。
在新的一行中，输出n个空格分隔的不同的整数表示p1。
在接下来的一行中，输出n个空格分隔的不同的整数表示p2。
爱丽丝将开始游戏。
对于每一轮，你必须读取两个整数u和v（1≤u,v≤n，u≠v）。你需要找到节点u和v之间唯一简单路径上的值的MEX。
为了进行查询，输出"? t l r"（不包含引号），使得t是1或2，1≤l≤r≤n。之后，你应该读取一个整数——对你查询的答案min_{i=l}^{r} a_{p_{t,i}}。
如果你要打印答案，输出"! x"（1≤x≤n，不包含引号）。之后，读取一个整数，通常等于1。
如果你收到-1而不是有效的回复，这意味着你的程序进行了无效的查询，超过了查询限制，或者在之前的测试案例中给出了错误的答案。你的程序必须立即终止，以获得"Wrong Answer"的判决。否则，你可能会得到任意的判决，因为你的解决方案会继续从关闭的流中读取。
在打印查询或答案后，不要忘记输出行尾并刷新输出。否则，你会得到"Idleness limit exceeded"。题目大意： 这是一个交互式问题。爱丽丝有一棵由n个节点组成的树T，节点编号从1到n。爱丽丝会向鲍勃展示T。观察T后，鲍勃需要告诉爱丽丝两个排列p1和p2，它们都是[1,2,...,n]的排列。 然后，爱丽丝会进行q轮游戏。 1. 爱丽丝会创建一个数组a，它是[0,1,...,n-1]的一个排列。节点v的值是a_v。 2. 爱丽丝会从T中选出两个节点u和v（1≤u,v≤n，u≠v）并告诉鲍勃。鲍勃需要找到节点u和v之间唯一简单路径上的值的MEX（最小排除数）。 3. 为了找到这个值，鲍勃可以向爱丽丝提出最多5个查询。在每次查询中，鲍勃应该给出三个整数t、l和r给爱丽丝，使得t是1或2，1≤l≤r≤n。爱丽丝会告诉鲍勃等于min_{i=l}^{r} a[p_{t,i}]的值。 注意，所有轮次都是相互独立的。特别是，a、u和v在不同轮次中可以不同。 鲍勃只知道HLD（重链剖分）解决方案，它需要每轮O(log(n))次查询。所以他需要你的帮助来赢得游戏。 输入输出数据格式： 每个测试包含多个测试案例。第一行包含一个整数t（1≤t≤10^4）——测试案例的数量。读取它。测试案例的描述接着这个数字。 每个测试案例的第一行包含两个正整数n和q（2≤n≤10^5，1≤q≤10^4）——树T的节点数和轮数。 接下来的n-1行每行包含两个整数u和v（1≤u,v≤n，u≠v）——表示节点u和v之间的一条边。保证给定的边构成一棵树。 每个测试案例以输出两个排列p1和p2开始。 在新的一行中，输出n个空格分隔的不同的整数表示p1。 在接下来的一行中，输出n个空格分隔的不同的整数表示p2。 爱丽丝将开始游戏。 对于每一轮，你必须读取两个整数u和v（1≤u,v≤n，u≠v）。你需要找到节点u和v之间唯一简单路径上的值的MEX。 为了进行查询，输出"? t l r"（不包含引号），使得t是1或2，1≤l≤r≤n。之后，你应该读取一个整数——对你查询的答案min_{i=l}^{r} a_{p_{t,i}}。 如果你要打印答案，输出"! x"（1≤x≤n，不包含引号）。之后，读取一个整数，通常等于1。 如果你收到-1而不是有效的回复，这意味着你的程序进行了无效的查询，超过了查询限制，或者在之前的测试案例中给出了错误的答案。你的程序必须立即终止，以获得"Wrong Answer"的判决。否则，你可能会得到任意的判决，因为你的解决方案会继续从关闭的流中读取。 在打印查询或答案后，不要忘记输出行尾并刷新输出。否则，你会得到"Idleness limit exceeded"。