luogu#P8998. [CEOI2022] Prize(交互,不可提交)

[CEOI2022] Prize(交互,不可提交)

题目描述

这是一道交互题。

Tomislav 在睡梦中想到了一个问题:给定两棵大小为 NN 的树,树上的节点按 1N1\sim N 分别编号,树则分别编号为树 11,树 22,树有边权,但是边权被隐藏了起来。

Tomislav 需要向交互库提供一个大小为 KK 的编号的子集 SS,在选择了这个集合后,小 C 可以问 QQ 个格式为 (a,b)(a,b) 的问题,定义 dt(x,y)d_t(x,y) 表示树 tt 上节点 xx 与节点 yy 的距离,ltl_t 表示树 tt 上节点 aa 与节点 bb 的 LCA,交互库会依次回答 d1(l1,a),d1(l1,b),d2(l2,a),d2(l2,b)d_1(l_1,a),d_1(l_1,b),d_2(l_2,a),d_2(l_2,b)

紧接着交互库会询问 TT 个格式为 (p,q)(p,q) 的问题,其中 p,qSp,q\in S,Tomislav 必须依次回答 d1(p,q)d_1(p,q)d2(p,q)d_2(p,q)

可怜的 Tomislav 并不会做,请你帮帮他。

输入格式

第一行输入四个整数 N,K,Q,TN,K,Q,T

接下来两行,每行 NN 个整数,第一行描述树 11,第二行描述树 22。描述方式为,给出 NN 个整数 p1,p2,,pNp_1,p_2,\ldots,p_N,如果 pip_i1-1,则 ii 为树的根,否则 pip_iii 的父亲。

接下来请输出 KK 个整数 x1,x2,,xKx_1,x_2,\ldots,x_K 表示小 C 给出的编号集合 SS,输出后请刷新缓冲区。

接下来你可以输出至多 QQ 行,格式为「? aa bb」,表示询问 (a,b)(a,b),当你的程序停止询问时,输出一行 「!」,表示结束询问,输出后请刷新缓冲区。

交互库会在你结束询问后返回所有询问的答案,分行返回,一行四个整数 d1(l1,a),d1(l1,b),d2(l2,a),d2(l2,b)d_1(l_1,a),d_1(l_1,b),d_2(l_2,a),d_2(l_2,b),表示询问的答案。

接下来输入 TT 行,每行两个整数 p,qp,q,表示一组交互库的询问。

你的程序需要回答这 TT 个询问,具体的,对于每一个询问,你需要输出一行两个整数 d1(p,q)d_1(p,q)d2(p,q)d_2(p,q),在你回答完所有的问题后,刷新缓冲区。

附加文件中会有一份示例程序,这份程序可以通过下面的样例,你可以根据这份程序理解交互过程。

提示

数据规模与约定

对于全部数据,保证所有边权为正整数且不超过 200020002K1052\le K\le 10^51Tmin(K2,105)1\le T\le \min(K^2,10^5)

Subtask 编号 特殊限制 分数
11 N=5×105N=5\times 10^5Q=K1Q=K-1,树 11 与树 22 完全相同,包括边权 1010
22 N=5×105N=5\times 10^5Q=2K2Q=2K-2 2525
33 N=5×105N=5\times 10^5K=200K=200Q=K1Q=K-1 1919
44 N=106N=10^6K=103K=10^3Q=K1Q=K-1 2222

交互示例

示例输出 示例输入
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