logo AlgoBeat OnlineJudge
登录 注册

#214130. [ICPC 2024 Nanjing R] 二叉树

内存限制:1024 MiB 时间限制:3000 ms 标准输入输出
题目类型:VJudge(洛谷) 评测方式:VJudge
上传者: 匿名

题目描述

给定一棵有 个节点的二叉树,您需要用至多 次询问找到树中的一个特殊节点 。也就是说, 是满足 的最大整数。

每次询问包含两个不同的节点 。裁判程序会输出一个整数 )表示询问的答案。令 表示从节点 到节点 的简单路径上有几条边。

  • ,则节点 离特殊节点更近。也就是说,
  • ,则节点 和节点 到特殊节点的距离相同。也就是说,
  • ,则节点 离特殊节点更近。也就是说,

请注意:裁判程序是适应性的。也就是说,每组测试数据的答案不是事先确定的。裁判程序可以根据您的询问决定特殊节点,只要它的答案与之前的询问和答案不冲突即可。

输入格式

有多组测试数据。第一行输入一个整数 表示测试数据组数。对于每组测试数据:

第一行输入一个整数 )表示二叉树中节点的数量。

对于接下来 行,第 行输入两个整数 ),表示第 个节点的左子节点和右子节点。若 ,则第 个节点没有左子节点;若 ,则第 个节点没有右子节点。

保证所有数据 之和不超过

交互方式

要提出询问,请输出一行。首先输出 ,之后跟一个空格,然后输出两个不同的由单个空格分隔的整数 )。在清空输出缓冲区之后,您的程序需要读入一个整数 ,表示对您的询问的回答。

要猜测特殊节点,请输出一行。首先输出 ,之后跟一个空格,然后输出一个整数 )表示特殊节点。在清空输出缓冲区之后,您的程序应该马上开始处理下一组测试数据。如果没有更多测试数据,您的程序应该立即退出。还请注意,猜测特殊节点不算一次询问。

清空输出缓冲区可以使用以下方式:

  • C 和 C++ 使用 (如果您使用 )或 (如果您使用 )。
  • Java 使用
  • Python 使用

样例

样例输入 1

2
5
0 0
1 5
2 4
0 0
0 0

1

0

2
0 2
0 0

2

样例输出 1








? 5 1

? 1 4

! 2



? 2 1

! 1