luogu#P8998. [CEOI2022] Prize(交互,不可提交)
[CEOI2022] Prize(交互,不可提交)
题目描述
这是一道交互题。
Tomislav 在睡梦中想到了一个问题:给定两棵大小为 的树,树上的节点按 分别编号,树则分别编号为树 ,树 ,树有边权,但是边权被隐藏了起来。
Tomislav 需要向交互库提供一个大小为 的编号的子集 ,在选择了这个集合后,小 C 可以问 个格式为 的问题,定义 表示树 上节点 与节点 的距离, 表示树 上节点 与节点 的 LCA,交互库会依次回答 。
紧接着交互库会询问 个格式为 的问题,其中 ,Tomislav 必须依次回答 和 。
可怜的 Tomislav 并不会做,请你帮帮他。
输入格式
第一行输入四个整数 。
接下来两行,每行 个整数,第一行描述树 ,第二行描述树 。描述方式为,给出 个整数 ,如果 为 ,则 为树的根,否则 为 的父亲。
接下来请输出 个整数 表示小 C 给出的编号集合 ,输出后请刷新缓冲区。
接下来你可以输出至多 行,格式为「?
」,表示询问 ,当你的程序停止询问时,输出一行 「!
」,表示结束询问,输出后请刷新缓冲区。
交互库会在你结束询问后返回所有询问的答案,分行返回,一行四个整数 ,表示询问的答案。
接下来输入 行,每行两个整数 ,表示一组交互库的询问。
你的程序需要回答这 个询问,具体的,对于每一个询问,你需要输出一行两个整数 和 ,在你回答完所有的问题后,刷新缓冲区。
附加文件中会有一份示例程序,这份程序可以通过下面的样例,你可以根据这份程序理解交互过程。
提示
数据规模与约定
对于全部数据,保证所有边权为正整数且不超过 ,,。
Subtask 编号 | 特殊限制 | 分数 |
---|---|---|
,,树 与树 完全相同,包括边权 | ||
, | ||
,, | ||
,, |
交互示例
示例输出 | 示例输入 |
---|---|
9 3 2 3 |
|
2 -1 2 1 1 5 1 4 5 |
|
9 4 5 5 7 3 -1 3 7 |
|
1 5 7 |
|
? 1 5 |
|
? 1 7 |
|
! |
|
0 2 5 3 |
|
0 3 5 0 |
|
1 7 |
|
7 5 |
|
5 1 |
|
3 5 |
|
5 3 |
|
2 8 |