#P13273. [集训队互测 2022day11]Tree

    ID: 12456 传统题 1000ms 256MiB 尝试: 2 已通过: 1 难度: 8 上传者: 标签>CF2500构造二分图论排序DFS分治树的重心

[集训队互测 2022day11]Tree

这是交互题,时间限制5s5s,空间限制1Gb1Gb

有一棵nn个节点的以11为根的树,你每次可以询问集合TT,令SuS_u表示uu子树内的点,d(u,v)d(u,v)表示uuvv路径上的边数,交互库会返回:

$$V=\{x|\exists u\in T,x\in S_u\}\\ D(T)=\sum_{i\in V,j\in V,i<j}d(i,j)$$

如果你返回的树和交互库同构,你将获得40%40\%的分数。

交互方式:

你需要实现std::vector<int> solve(int n);其中nn是节点数,返回的vector里面依次存储2n2\sim n的父亲节点,注意:不保证父亲节点编号小于子节点。

你可以使用int query(std::vector<int> T);来询问,意义如上。

正式评测时交互库仅添加防作弊措施,运行效率与下发文件相同。

本地测试时,交互库读入为:第一行一个整数nn,第二行n1n-1个整数分别表示2n2\sim n的父亲。

例:

6
1 2 3 1 2

询问:

query({1})=31
query({3,5})=8
query({3})=1

返回:

{1,2,3,1,2}:  score=1.0
{1,2,3,2,1}:  score=0.4
{1,1,1,1,1}:  score=0.0

数据范围及子任务:

n1000n\le 1000,下面TT表示你询问次数的上界。

AA特殊性质满足:这是一棵二叉树。

BB特殊性质满足:树随机,随机方式为:随机生成一个排列pp,满足p1=1p_1=1,然后令fpif_{p_i}p1i1p_{1\sim i-1}内随机生成。