AT_arc142_c [ARC142C] Tree Queries
题目描述
有一棵包含 $N$ 个顶点的树，每个顶点编号为 $1,\ldots,N$。
对于每一对整数 $u,v\,\ (1\leq u,v\leq N)$，定义顶点 $u$ 和顶点 $v$ 之间的距离 $d_{u,v}$ 为：
- 在连接顶点 $u$ 和顶点 $v$ 的最短路径上包含的边的数量。
你可以进行 $0$ 次以上、$2N$ 次以下的如下询问：
- 指定满足 $1\leq u,v\leq N$ 且 $u+v>3$ 的整数 $u,v$，询问顶点 $u$ 和顶点 $v$ 的距离 $d_{u,v}$。
请你求出顶点 $1$ 和顶点 $2$ 之间的距离 $d_{1,2}$。
输入格式
**本题为交互题**（你的程序需要与评测程序通过输入输出进行交互）。
首先，你的程序会从标准输入读入一个正整数 $N$。
> $N$
之后，你可以进行询问。
每次询问请按如下格式输出到标准输出（末尾需换行）：
> ? $u$ $v$
如果询问合法，你会从标准输入读入该询问的答案 $d_{u,v}$。
> $d_{u,v}$
如果你的询问格式错误、询问次数超限等导致询问被判为不合法，你会收到 $-1$ 作为回应。
```
-1
```
此时，评测程序会立即终止，判定你的提交为不正确。你的程序也应立即终止。
当你确定 $d_{1,2}$ 的值后，请按如下格式输出答案（末尾需换行）：
> ! $d_{1,2}$
输出格式
见上文交互格式说明。
说明/提示
## 限制
- $3\leq N\leq 100$
- $N$ 是整数
- 树在交互开始前已确定
## 注意事项
- **每次输出后请务必刷新标准输出，否则可能会因超时（TLE）被判为不正确。**
- 输出答案后（或收到 $-1$ 后）请立即正常退出程序，否则评测结果不确定。
- 输出格式不正确时，评测结果不确定。
- 特别注意，不要输出多余的换行，否则会被判为格式错误。
## 输入输出样例
以下为当树结构如图所示时的交互样例：
输入 输出 说明
`3` 首先给出整数 $N$。
`? 1 3` 第一次询问，询问顶点 $1,3$ 的距离。
`1` 返回顶点 $1,3$ 的距离。
`? 2 2` 第二次询问，询问顶点 $2,2$ 的距离。
`0` 返回顶点 $2,2$ 的距离。
`? 2 3` 第三次询问，询问顶点 $2,3$ 的距离。
`1` 返回顶点 $2,3$ 的距离。
`? 3 1` 第四次询问，询问顶点 $3,1$ 的距离。
`1` 返回顶点 $3,1$ 的距离。
`? 3 2` 第五次询问，询问顶点 $3,2$ 的距离。
`1` 返回顶点 $3,2$ 的距离。
`? 2 2` 第六次询问，询问顶点 $2,2$ 的距离。
`0` 返回顶点 $2,2$ 的距离。
`! 2` 输出顶点 $1,2$ 的距离并结束。实际树中顶点 $1,2$ 的距离为 $2$，因此本次提交可以通过。
由 ChatGPT 4.1 翻译