配点 : 1000 点
問題文
这是一个互动问题。
Niwango,dwango 员工, N 存在于顶点树中。 在这棵树的顶端 它们的编号最大为 1 从 N 。 这棵树 i 第一条边是顶点 两个方向连接 a_i 和顶点 询问 b_i 的长度 这是 1 一侧。 二王后君 任意顶点的度数 5 小于或等于 我知道。
二万吾君的房子位于其中一棵树的顶部,但二万吾君忘记了他的房子在哪里。
Niwango-kun 是一个自制程序,具有最大
我想问 Q 次来确定房子所在的顶点。
到节目 2 顶点数 u,v ,则会显示距离房屋所在顶点最近的顶点编号。
但是,如果两个顶点到房屋所在顶点的距离相同
显示 0 。
制約
- 2 \leq N \leq 2{,}000
- Q = 14
- 1 \leq a_i,b_i \leq N
- 给定的图是一棵树
- 任意顶点的度数 5 以下
部分点
- 任意顶点的度数 2 如果您对以下数据集的回答正确,400 点。
入出力
首先,输入是从标准输入按以下格式给出的:
N Q
a_1 b_1
:
a_{N-1} b_{N-1}
然后按以下格式输出问题:
? u v
在这里, 必须是小于或等于u,v 表示 1 以上 N 的整数。 然后从标准输入中以以下格式给出问题的答案:
ans
在这里, 必须是小于或等于ans 表示 u,v,0 。 每个值代表以下含义:
- u:u 和 我讨厌 v 中距离房屋所在顶点最近的一个 u 是
- v:u 和 我讨厌 v 中距离房屋所在顶点最近的一个 v 是
- 0:u 和 我讨厌 v 与房屋所在顶点的距离相同
最后,按以下格式打印您的答案:
! x
这里 如果你知道 x 必须是房屋所在的顶点。
法官
- 打印后刷新标准输出。如果您不遵守
有一种可能性是
TLE。 - 打印答案后立即退出程序。法官在不遵守规定的情况下的行为是不确定的。
- 输出答案错误时的行为未定义(
WA)。
入出力例
这意味着在下面的树中,顶点 这是 Niwango 的房子位于 3 时的输入/输出示例。
| 输入 | 输出 |
|---|---|
| 6 14 1 2 5 2 3 1 3 6 1 4 |
|
| ? 4 5 | |
| 4 | |
| ? 1 6 | |
| 0 | |
| ? 6 5 | |
| 6 | |
| ! 3 |
- 頂点 4,5 中,顶点 顶点最接近 3 顶点最接近 4 所以 4 。
- 頂点 1,6 是顶点 由于与 3 的距离相同,0 。
- 頂点 6,5 中,顶点 顶点最接近 3 顶点最接近 6 所以 6 。
- 房子所在的顶点 3 我回答了。 答案是正确的,因为正确答案的输出次数为14 次或更少。