← 返回题目列表

AtCoder · arc142_c

C. 树查询

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

分数: 500 点

问题陈述

有一棵树 N 顶点,编号 1, \ldots, N.
对于每对整数 u,v\, (1 \leq u,v \leq N),距离 d_{u,v} 顶点之间 u, v 定义如下。

  • 连接顶点的最短路径中包含的边数 u 和 v.

您可以询问 0 和 2N 问题(含)采用以下形式。

  • 询问距离 d_{u,v} 顶点之间 u,v 对于整数 u,v 您选择的 1\leq u,v \leq N 和 u+v>3.

求距离 d_{1,2} 顶点之间 1,2.

约束

  • 3 \leq N \leq 100
  • N 是一个整数。
  • 树是在程序和法官之间开始交互之前确定的。

输入和输出

这是一个交互式任务,其中您的程序和法官通过输入和输出进行交互。

首先,你的程序被赋予一个正整数 来自标准输入的 N :

N

然后,你可以提问。
问题应按以下格式打印(末尾有换行符):

? u v

如果问题有效,则回复 d_{u,v} 由标准输入给出:

d_{u,v}

如果问题被判定为无效,例如,由于格式错误或您问了太多问题,您会得到 -1 而不是响应:

-1

此时,您的提交已被判定为不正确。然后法官的程序终止;你的也应该如此,希望如此。

当你找到答案时 d_{1,2},按以下格式将其打印到标准输出(末尾有换行符):

! d_{1,2}

通知

  • 每次输出后刷新标准输出。否则,您可能会得到 TLE 判决。
  • 打印答案后(或收到 -1),立即正常终止程序。否则,判决将是不确定的。
  • 对于格式错误的输出情况的判决是不确定的。
  • 具体来说,请注意,过多的换行符也会被视为格式错误的输出。

示例输入和输出

以下是此图中所示树的示例交互。

输入 输出 说明
3 交互从整数开始 N.
? 1 3 作为 1-st问题,你问顶点之间的距离 1 和 3.
1 顶点之间的距离 返回 1,3 。
? 2 2 作为 2-第一个问题,你问顶点之间的距离 2 和 2.
0 顶点之间的距离 返回 2,2 。
? 2 3 作为 3-rd问题,你问顶点之间的距离 2 和 3.
1 顶点之间的距离 返回 2,3 。
? 3 1 作为 4- 第题,你问顶点之间的距离 3 和 1.
1 顶点之间的距离 返回 3,1 。
? 3 2 作为 5- 第题,你问顶点之间的距离 3 和 2.
1 顶点之间的距离 返回 3,2 。
? 2 2 作为 6- 第题,你问顶点之间的距离 2 和 2.
0 顶点之间的距离 返回 2,2 。
! 2 你猜测顶点之间的距离 1,2 并终止。他们之间的实际距离是 2,所以你会得到 AC 判决。