Lost Nodes

题意翻译

这是一道**交互题**。 给你一棵包含 $n$ 个节点的树。你需要猜测出这棵树上的两个特殊节点 $a,b$（$a$ 不一定与 $b$ 不同）。 首先，你会被告知一个整数 $f$，满足节点 $f$ 是节点 $a,b$ 之间的简单路径上的一点。 接下来你可以进行询问，具体的，每次给定整数 $r$，交互器会给你当树的根节点为 $r$ 时，节点 $a,b$ 的最近公共祖先是哪个节点。 特别的，在给定树的形态之后，你需要先给出在所有 $a,b,f$ 的可能的取值中，至少需要多少次询问才能保证得出特殊节点的编号。 $1\leq n\leq10^5;1\leq a,b,f\leq n$ 且节点 $f$ 在节点 $a,b$ 之间的简单路径上（包括节点 $a,b$）。 **交互格式如下：** 首先输入整数 $n$，表示树的节点数。接下来 $n-1$ 行，每行两个整数 $u,v(1\leq u,v\leq n,u\not=v)$ 表示节点 $u,v$ 之间有一条边。我们保证给定的是一棵树。 接下来，你需要先输出对于这棵树，确定 $a,b$ 所需要的最小询问次数，我们保证这个最小询问次数 $\in[0,n]$，接下来你的询问次数将被限制在你所输出的这个最大询问次数内。 接下来输入 $f$。之后你便可以开始询问，询问格式为 `? r`，你需要满足 $1\leq r\leq n$。如果你认为你得到了答案，按照 `! a b` 的格式输出，$a,b$ 的顺序随意。 答案错误、程序所输出的询问次数过多、询问不合法均会导致 `Wrong Answer` 的评测结果。同时，请注意刷新缓冲区。

题目描述

This is an interactive problem. As he qualified for IOI this year, Little Ericyi was given a gift from all his friends: a tree of $ n $ nodes! On the flight to IOI Little Ericyi was very bored, so he decided to play a game with Little Yvonne with his new tree. First, Little Yvonne selects two (not necessarily different) nodes $ a $ and $ b $ on the tree (without telling Ericyi), and then gives him a hint $ f $ (which is some node on the path from $ a $ to $ b $ ). Then, Little Ericyi is able to ask the following question repeatedly: - If I rooted the tree at node $ r $ (Ericyi gets to choose $ r $ ), what would be the [Lowest Common Ancestor](https://en.wikipedia.org/wiki/Lowest_common_ancestor) of $ a $ and $ b $ ? Little Ericyi's goal is to find the nodes $ a $ and $ b $ , and report them to Little Yvonne. However, Little Yvonne thought this game was too easy, so before he gives the hint $ f $ to Little Ericyi, he also wants him to first find the maximum number of queries required to determine $ a $ and $ b $ over all possibilities of $ a $ , $ b $ , and $ f $ assuming Little Ericyi plays optimally. Little Ericyi defines an optimal strategy as one that makes the minimum number of queries. Of course, once Little Ericyi replies with the maximum number of queries, Little Yvonne will only let him use that many queries in the game. The tree, $ a $ , $ b $ , and $ f $ are all fixed before the start of the game and do not change as queries are made.

输入输出格式

输入格式

输出格式

First read a line containing the integer $ n $ ( $ 1 \le n \le 10^5 $ ), the number of nodes in the tree. The next $ n−1 $ lines describe Little Ericyi's tree. These lines contain two integers $ u $ and $ v $ ( $ 1 \le u,v \le n $ ) denoting an edge between $ u $ and $ v $ ( $ u \neq v $ ). It is guaranteed that these edges form a tree. After that you should output $ k $ , the maximum number of queries needed to determine $ a $ and $ b $ over all possibilities of $ a $ , $ b $ , and $ f $ assuming Little Ericyi plays optimally. You should output end of line and flush the output after printing $ k $ . After that read a line containing the integer $ f $ ( $ 1 \le f \le n $ ) — the hint: a node on the path from $ a $ to $ b $ , inclusive. After that, you can start making queries. You will be limited to making at most $ k $ queries, where $ k $ is the number you printed. Each query is made in the format "? r", where $ r $ is an integer $ 1 \le r \le n $ denoting the root node you want for the query. You will then receive an integer $ x $ ( $ 1 \le x \le n $ ), the Lowest Common Ancestor of $ a $ and $ b $ if the tree was rooted at $ r $ . When your program has found the nodes $ a $ , $ b $ , report the answer in the following format: "! a b", where $ a $ and $ b $ are the two hidden nodes and terminate your program normally immediately after flushing the output stream. You may output $ a $ and $ b $ in any order. After printing a query do not forget to output end of 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. If at any point you make an invalid output or make more than $ k $ queries, the interaction will terminate and you will receive a Wrong Answer verdict. An invalid output is defined as either an invalid query or a value of $ k $ less than $ 0 $ or greater than $ n $ . Hacks To hack a solution, use the following format: The first line contains the integer $ n $ ( $ 1 \le n \le 10^5 $ ). The next $ n−1 $ lines contain two integers $ u $ and $ v $ ( $ 1 \le u,v \le n $ ) denoting an edge between $ u $ and $ v $ ( $ u \neq v $ ). These $ n-1 $ edges must form a tree. The next line of input contains the nodes $ a $ and $ b $ ( $ 1 \le a,b \le n $ ), separated by a space. The final line of input contains the integer $ f $ ( $ 1 \le f \le n $ ). Node $ f $ should be on the simple path from $ a $ to $ b $ (inclusive).

输入输出样例

输入样例 #1

4
3 2
2 1
2 4

1

1

2

2

输出样例 #1

3

? 1

? 2

? 3

! 4 1

输入样例 #2

5
3 1
1 4
4 5
4 2

1

4

1

4

输出样例 #2

3

? 4

? 1

? 5

! 1 4

说明

Here is the the tree from the first sample interaction. Nodes $ a $ and $ b $ are highlighted. Notice that $ a $ and $ b $ can be output in any order. Additionally, here are the answers to querying every single node $ 1,2,\ldots,n $ for your convenience: - $ 1 $ : $ 1 $ - $ 2 $ : $ 2 $ - $ 3 $ : $ 2 $ - $ 4 $ : $ 4 $ \_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_ Here is the the tree from the second sample interaction. Again, nodes $ a $ and $ b $ are highlighted. Lastly, here are the answers to querying every single node $ 1,2,\ldots,n $ (in example $ 2 $ ) for your convenience: - $ 1 $ : $ 1 $ - $ 2 $ : $ 4 $ - $ 3 $ : $ 1 $ - $ 4 $ : $ 4 $ - $ 5 $ : $ 4 $