309934: CF1761G. Centroid Guess
Memory Limit：512 MB
Time Limit：4 S
Judge Style：Text Compare
Creator：
Submit：0
Solved：0
Description
Centroid Guess
题意翻译
- 给定一棵 $n$ 个点的树，保证重心唯一。 - 你可以询问不超过 $m$ 次任意两点的距离。 - 求出树的重心。 - $3\leq n\leq 7.5\times 10^4$，$m=2\times 10^5$。 - 本题共 $500$ 个测试点。题目描述
This in an interactive problem. There is an unknown tree consisting of $ n $ nodes, which has exactly one centroid. You only know $ n $ at first, and your task is to find the centroid of the tree. You can ask the distance between any two vertices for at most $ 2\cdot10^5 $ times. Note that the interactor is not adaptive. That is, the tree is fixed in each test beforehand and does not depend on your queries. A vertex is called a centroid if its removal splits the tree into subtrees with at most $ \lfloor\frac{n}{2}\rfloor $ vertices each.输入输出格式
输入格式
The only line of the input contains an integer $ n $ ( $ 3\le n\le 7.5\cdot10^4 $ ) — the number of nodes in the tree.
输出格式
Start interaction by reading $ n $ . To ask a query about the distance between two nodes $ u, v $ ( $ 1 \le u, v \le n $ ), output "? u v". If you determine that the centroid of the tree is $ x $ , use "! x" to report. After printing a query, do not forget to output the end of a 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 are disabled in this problem. It's guaranteed that there are at most $ 500 $ tests in this problem.
输入输出样例
输入样例 #1
5
2
1
2
3
1
1
1输出样例 #1
? 1 2
? 1 3
? 1 4
? 1 5
? 2 3
? 3 4
? 4 5
! 3说明
Here is an image of the tree from the sample. Input
题意翻译
- 给定一棵 $n$ 个点的树，保证重心唯一。 - 你可以询问不超过 $m$ 次任意两点的距离。 - 求出树的重心。 - $3\leq n\leq 7.5\times 10^4$，$m=2\times 10^5$。 - 本题共 $500$ 个测试点。Output
**树的重心猜测**
**题意翻译**
- 给定一棵有 $n$ 个点的树，保证重心唯一。
- 你可以询问不超过 $m$ 次任意两点的距离。
- 求出树的重心。
- $3 \leq n \leq 7.5 \times 10^4$，$m = 2 \times 10^5$。
- 本题共 $500$ 个测试点。
**题目描述**
这是一个交互问题。
有一棵未知的树，包含 $n$ 个节点，恰好有一个重心。起初你只知道 $n$，你的任务是找到这棵树的重心。
你可以最多询问 $2 \cdot 10^5$ 次任意两点之间的距离。
注意，交互器不是自适应的。也就是说，树在每个测试中预先固定，不依赖于你的查询。
如果一个节点的移除可以将树分成至多有 $\lfloor \frac{n}{2} \rfloor$ 个节点的子树，那么这个节点被称为重心。
**输入输出格式**
**输入格式**
输入只有一行，包含一个整数 $n$ ($3 \leq n \leq 7.5 \times 10^4$) —— 树中节点的数量。
**输出格式**
开始交互时读取 $n$。
为了询问两个节点 $u, v$ ($1 \leq u, v \leq n$) 之间的距离，输出 "? u v"。
如果你确定树的重心是 $x$，使用 "! x" 来报告。
在输出一个查询后，不要忘记输出行尾并刷新输出。否则，你将得到超时限制。为此，使用：
- 在 C++ 中使用 `fflush(stdout)` 或 `cout.flush()`；
- 在 Java 中使用 `System.out.flush()`；
- 在 Pascal 中使用 `flush(output)`；
- 在 Python 中使用 `stdout.flush()`；
- 查看其他语言的文档。
本题中禁用了 Hack。
保证这个问题最多有 $500$ 个测试点。
**输入输出样例**
**输入样例 #1**
```
5
2
1
2
3
1
1
1
```
**输出样例 #1**
```
? 1 2
? 1 3
? 1 4
? 1 5
? 2 3
? 3 4
? 4 5
! 3
```
**说明**
这是样例中树的图像。
**树的重心猜测** **题意翻译** - 给定一棵有 $n$ 个点的树，保证重心唯一。 - 你可以询问不超过 $m$ 次任意两点的距离。 - 求出树的重心。 - $3 \leq n \leq 7.5 \times 10^4$，$m = 2 \times 10^5$。 - 本题共 $500$ 个测试点。 **题目描述** 这是一个交互问题。 有一棵未知的树，包含 $n$ 个节点，恰好有一个重心。起初你只知道 $n$，你的任务是找到这棵树的重心。 你可以最多询问 $2 \cdot 10^5$ 次任意两点之间的距离。 注意，交互器不是自适应的。也就是说，树在每个测试中预先固定，不依赖于你的查询。 如果一个节点的移除可以将树分成至多有 $\lfloor \frac{n}{2} \rfloor$ 个节点的子树，那么这个节点被称为重心。 **输入输出格式** **输入格式** 输入只有一行，包含一个整数 $n$ ($3 \leq n \leq 7.5 \times 10^4$) —— 树中节点的数量。 **输出格式** 开始交互时读取 $n$。 为了询问两个节点 $u, v$ ($1 \leq u, v \leq n$) 之间的距离，输出 "? u v"。 如果你确定树的重心是 $x$，使用 "! x" 来报告。 在输出一个查询后，不要忘记输出行尾并刷新输出。否则，你将得到超时限制。为此，使用： - 在 C++ 中使用 `fflush(stdout)` 或 `cout.flush()`； - 在 Java 中使用 `System.out.flush()`； - 在 Pascal 中使用 `flush(output)`； - 在 Python 中使用 `stdout.flush()`； - 查看其他语言的文档。 本题中禁用了 Hack。 保证这个问题最多有 $500$ 个测试点。 **输入输出样例** **输入样例 #1** ``` 5 2 1 2 3 1 1 1 ``` **输出样例 #1** ``` ? 1 2 ? 1 3 ? 1 4 ? 1 5 ? 2 3 ? 3 4 ? 4 5 ! 3 ``` **说明** 这是样例中树的图像。 
**题意翻译**
- 给定一棵有 $n$ 个点的树，保证重心唯一。
- 你可以询问不超过 $m$ 次任意两点的距离。
- 求出树的重心。
- $3 \leq n \leq 7.5 \times 10^4$，$m = 2 \times 10^5$。
- 本题共 $500$ 个测试点。
**题目描述**
这是一个交互问题。
有一棵未知的树，包含 $n$ 个节点，恰好有一个重心。起初你只知道 $n$，你的任务是找到这棵树的重心。
你可以最多询问 $2 \cdot 10^5$ 次任意两点之间的距离。
注意，交互器不是自适应的。也就是说，树在每个测试中预先固定，不依赖于你的查询。
如果一个节点的移除可以将树分成至多有 $\lfloor \frac{n}{2} \rfloor$ 个节点的子树，那么这个节点被称为重心。
**输入输出格式**
**输入格式**
输入只有一行，包含一个整数 $n$ ($3 \leq n \leq 7.5 \times 10^4$) —— 树中节点的数量。
**输出格式**
开始交互时读取 $n$。
为了询问两个节点 $u, v$ ($1 \leq u, v \leq n$) 之间的距离，输出 "? u v"。
如果你确定树的重心是 $x$，使用 "! x" 来报告。
在输出一个查询后，不要忘记输出行尾并刷新输出。否则，你将得到超时限制。为此，使用：
- 在 C++ 中使用 `fflush(stdout)` 或 `cout.flush()`；
- 在 Java 中使用 `System.out.flush()`；
- 在 Pascal 中使用 `flush(output)`；
- 在 Python 中使用 `stdout.flush()`；
- 查看其他语言的文档。
本题中禁用了 Hack。
保证这个问题最多有 $500$ 个测试点。
**输入输出样例**
**输入样例 #1**
```
5
2
1
2
3
1
1
1
```
**输出样例 #1**
```
? 1 2
? 1 3
? 1 4
? 1 5
? 2 3
? 3 4
? 4 5
! 3
```
**说明**
这是样例中树的图像。
**树的重心猜测** **题意翻译** - 给定一棵有 $n$ 个点的树，保证重心唯一。 - 你可以询问不超过 $m$ 次任意两点的距离。 - 求出树的重心。 - $3 \leq n \leq 7.5 \times 10^4$，$m = 2 \times 10^5$。 - 本题共 $500$ 个测试点。 **题目描述** 这是一个交互问题。 有一棵未知的树，包含 $n$ 个节点，恰好有一个重心。起初你只知道 $n$，你的任务是找到这棵树的重心。 你可以最多询问 $2 \cdot 10^5$ 次任意两点之间的距离。 注意，交互器不是自适应的。也就是说，树在每个测试中预先固定，不依赖于你的查询。 如果一个节点的移除可以将树分成至多有 $\lfloor \frac{n}{2} \rfloor$ 个节点的子树，那么这个节点被称为重心。 **输入输出格式** **输入格式** 输入只有一行，包含一个整数 $n$ ($3 \leq n \leq 7.5 \times 10^4$) —— 树中节点的数量。 **输出格式** 开始交互时读取 $n$。 为了询问两个节点 $u, v$ ($1 \leq u, v \leq n$) 之间的距离，输出 "? u v"。 如果你确定树的重心是 $x$，使用 "! x" 来报告。 在输出一个查询后，不要忘记输出行尾并刷新输出。否则，你将得到超时限制。为此，使用： - 在 C++ 中使用 `fflush(stdout)` 或 `cout.flush()`； - 在 Java 中使用 `System.out.flush()`； - 在 Pascal 中使用 `flush(output)`； - 在 Python 中使用 `stdout.flush()`； - 查看其他语言的文档。 本题中禁用了 Hack。 保证这个问题最多有 $500$ 个测试点。 **输入输出样例** **输入样例 #1** ``` 5 2 1 2 3 1 1 1 ``` **输出样例 #1** ``` ? 1 2 ? 1 3 ? 1 4 ? 1 5 ? 2 3 ? 3 4 ? 4 5 ! 3 ``` **说明** 这是样例中树的图像。 