← 返回题目列表

AtCoder · dwacon2018_prelims_e

E. 为二王后君找房子

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

配点 : 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 时的输入/输出示例。

9a1e6749a8c427dfca8d1bb6d28204c8.png
输入 输出
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 次或更少。