#P13273. [集训队互测 2022day11]Tree
[集训队互测 2022day11]Tree
这是交互题,时间限制,空间限制。
有一棵个节点的以为根的树,你每次可以询问集合,令表示子树内的点,表示到路径上的边数,交互库会返回:
$$V=\{x|\exists u\in T,x\in S_u\}\\ D(T)=\sum_{i\in V,j\in V,i<j}d(i,j)$$如果你返回的树和交互库同构,你将获得的分数。
交互方式:
你需要实现std::vector<int> solve(int n);其中是节点数,返回的vector里面依次存储的父亲节点,注意:不保证父亲节点编号小于子节点。
你可以使用int query(std::vector<int> T);来询问,意义如上。
正式评测时交互库仅添加防作弊措施,运行效率与下发文件相同。
本地测试时,交互库读入为:第一行一个整数,第二行个整数分别表示的父亲。
例:
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
数据范围及子任务:
,下面表示你询问次数的上界。
特殊性质满足:这是一棵二叉树。
特殊性质满足:树随机,随机方式为:随机生成一个排列,满足,然后令在内随机生成。