「2021 集训队互测」Tree

ID: 1868

传统题

5000ms

1024MiB

难度: (无)

上传者:

标签>

交互题

集训队互测

2021

题目描述

这是一道交互题。

有一棵 $n$ 个节点的以 $1$ 为根的树，你每次可以询问集合 $T$ ，令 $S_u$ 表示 $u$ 子树内的点， $d(u,v)$ 表示 $u$ 到 $v$ 路径上的边数，交互库会返回：

$$\begin{aligned} V&=\{x \mid \exists u\in T,x\in S_u\}\\ D(T)&=\sum_{i\in V,j\in V,i < j}d(i,j) \end{aligned} $$

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

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

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

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

本地测试时，交互库读入为：第一行一个整数 $n$ ，第二行 $n-1$ 个整数分别表示 $2\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

$n\leq 1000$ ，下面 $T$ 表示你询问次数的上界。

A 特殊性质满足：这是一棵二叉树。
B 特殊性质满足：树随机，随机方式为：随机生成一个排列 $p$ ，满足 $p_1=1$ ，然后令 $f_{p_i}$ 在 $p_{1\sim i-1}$ 内随机生成。