← 返回题目列表

Codeforces · 1444/E

E. 寻找顶点

中文机器翻译题面 查看原题

这是一个交互问题。

给你一棵树——无环的连通无向图。树的一个顶点是特殊的,你必须找到哪一个。你可以按照以下形式提出问题:给定树的一条边,哪个端点距离特殊顶点更近,意味着哪个端点到特殊顶点的最短路径包含更少的边。对于给定的树,您必须通过在最坏情况下询问最少数量的问题来找到特殊顶点。

请注意,交互器可能不会提前固定特殊顶点:它可能会将顶点更改为任何其他顶点,但要求与之前给出的答案一致。

输入

给你一个整数 $$$n$$$ ($$$2 \le n \le 100$$$) — 树中的顶点数。

下面的 $$$n-1$$$ 行每行包含两个整数,$$$u$$$ 和 $$$v$$$ ($$$1 \le u, v \le n$$$),表示树中连接 $$$u$$$ 和 $$$v$$$ 的边。保证给定的边形成一棵树。

互动

读取输入数据后,就可以开始查询了。有两种可能的查询:

1. "?$$$u$$$ $$$v$$$" — 询问一条边 $$$(u, v)$$$ ($$$1 \le u, v \le n$$$) 哪个端点更接近特殊顶点。该查询的答案是端点之一。请注意,$$$u$$$ 和 $$$v$$$ 必须通过边连接,因此它们到特殊顶点的距离不能相同。
2.“!$$$u$$$”— 表示您找到了特殊顶点。程序完成此操作后,必须立即终止。

不要忘记输出行尾并刷新输出。否则您将得到超出空闲限制的判决。要刷新输出,您可以使用:

- C++ 中的 fflush(stdout) 或 cout.flush();
- Java 中的 System.out.flush();
- 帕斯卡刷新(输出);
- Python 中的 sys.stdout.flush() ;
- 请参阅其他语言的文档。

如果您询问的查询数量超过了给定树在最坏情况下所需的数量,您将得到错误的答案。

示例

输入 #1

5
1 2
2 3
3 4
4 5
3
2
1

输出 #1

? 3 4
? 2 3
? 1 2
! 1

输入 #2

5
2 1
3 1
4 1
5 1
1
1
4

输出 #2

? 1 2
? 1 3
? 1 4
! 4

注意

此任务禁止黑客攻击。