[CTS2022] WBTT

**这是一道交互题。** #### 本地测试需 #include <long.h> #### 提交时请采用以下模板，而不 include long.h，具体方法就是直接把这个模板放在自己代码里面，然后需要完善题目中要求的函数。 ```cpp struct sethash{ int val; void encode(); void decode(); void operator=(int x); }; struct infoset{ sethash sum; int sz; int size()const{ return sz; } }; extern const infoset emptyset; infoset merge(const infoset&a,const infoset&b); void report(infoset p); void init(int id,int n,int q,vector<int>dad,vector<infoset>ve); void modify(int x,int y); void ask(int x,int y); ``` *** 伟大的科学家欣准备建造强人工智能隆统治世界。在输入一些越南的算法竞赛题作为训练集后，她发现隆自动生成了一个新的问题，并给出了一份解答。同时隆还将测试集中30%的输入数据归约到了这个问题。 欣连忙将这个问题抄录如下： 给定一棵有根树，你需要支持两种操作 * 查询树链元素和 * 将一个点的父亲改成另一个点 “这个问题并不强啊，为什么能解决测试集中30%的问题呢？”欣心里想。 在关闭训练结果页面前，欣突然发现，隆给出的这个问题中，信息合并的代价并不是 $O(1)$ 的。 欣陷入了沉思，发现自己并不会这道题。 为了知道这题有多难，欣将这题放到了您的面前。

你需要维护一棵以 $1$ 为根的有根树。这棵树有 $n$ 个点。初始时对于所有 $2 \le i \le n$，点 $i$ 有个父亲 $p_i$，保证 $p_i \lt i$。 一开始你有 $n$ 个集合 $\{1\},\{2\},\cdots,\{n\} $。对于任意两个集合 $A$ 和 $B$，如果 $A \cap B=\empty$，那么你可以通过一次操作，消耗 $|A|+|B|$ 的代价，获得集合 $A \cup B$。 之后有 $q$ 次操作。每次操作有两种类型 * `0 a b` 记树上 $a$ 到 $b$ 之间的路径上的点构成的点集为 $S$。你需要将 $S$ 表示为 $\cup_{i=1}^{k}A_i$，需要满足 $A_i$ 是你已经获得的集合，且 $\forall i \neq j,A_i \cap A_j=\empty$。用 $(A_1,A_2,\cdots,A_k) $ 回答一次询问的代价为 $k$。 * `1 a b` 表示将点 $a$ 的父亲改为 $b$，保证 $a \gt 1$，且修改后这 $n$ 个点仍构成一棵树，但**不保证 $a \gt b$ ** 。你可以在这次操作中新生成一些集合用以应对之后的询问。 记你整个程序运行过程中消耗的总代价为 $C_1$，单次操作消耗代价最大值为 $C_2$。每个子任务会根据 $C_1,C_2$ 的大小按照一定方式给分。

### 实现细节 头文件中定义了数据类型 `infoset`，用于存储你获得的集合。 该类型包括成员函数 `size()`，表示集合大小。**头文件还为你提供了表示空集的常量 `emptyset`**。 此外你还可以调用如下函数： `infoset merge(const infoset&A,const infoset&B);` * 以一定代价生成一个新集合 $A \cup B$ * 注意你可以多次重复生成同一个集合，并且需要多次计入代价 `void report(infoset A);` * 你仅可以在查询操作过程中调用该函数，表示你需要消耗 $1$ 的代价在最终的并中添加一个集合 $A$ 你不需要，也不应该实现主函数。你需要实现如下几个函数： `void init(int id,int n,int q,vector<int>dad,vector<infoset>ve);` * 你可以在 $q$ 次操作开始前预处理一些信息 * 在该函数中消耗的代价不会计入**单次操作消耗代价最大值**，但会计入**整个程序运行过程中消耗的总代价** * `id` 表示子任务编号，`n` 表示总点数，`q`表示总操作数 * `dad` 的大小为 $n-1$，`dad[i]` 表示初始时刻点 $i+2$ 的父亲 * `ve` 的大小为 $n$，`ve[i]` 表示初始集合 $\{i+1\}$ `void modify(int x,int y);` * 执行一次修改操作，将点 $x$ 的父亲置为点 $y$ `void ask(int x,int y);` * 执行一次查询操作，询问 $x$ 到 $y$ 的树链信息 * 你需要调用若干次 `report` 来回答询问，本次询问结束时交互库会检查你汇报的所有集合 $A$ 是否满足条件 评测时，交互库会先调用 `init` 一次，然后调用 `modify` 和 `ask` 总共 $q$ 次。 本题保证树的形态与执行的操作在交互开始之前已经完全确定，不会根据和你的程序的交互过程动态构造，因此题目中的交互操作都是确定性的，你不需要关心这些操作在交互库中的具体实现。 评测时交互库会使用特殊的实现方式，单个 `infoset` 类型的变量会恒定消耗 $8$ 字节内存，请保证你的程序运行过程中没有过多的 `infoset` 类型变量同时存在。 保证在调用次数限制下，交互库运行所需的时间不超过 2s；交互库本身所消耗的内存不超过16MB。

### 测试程序方式 下发文件中的 `grader.cpp` 是我们提供的交互库参考实现，最终测试时所用的交互库实现与该参考实现有所不同，因此选手的解法不应该依赖交互库实现。 你需要使用如下命令编译得到可执行程序： `g++ grader.cpp long.cpp -o long -static -O2 -std=c++14` 对于编译得到的可执行程序： - 可执行文件将从标准输入读入以下格式的数据： - 第一行包含一个整数 $id$ ，表示子任务编号 - 第二行包含两个整数 $n,q$，表示总点数和总操作数 - 第三行包含 $n-1$ 个整数，分别表示第 $2$ 至$n$ 个点的父亲节点编号 - 接下来 $q$ 行，每行三个整数 $op,x,y$，描述一次操作。$op=0$ 表示这是一次询问操作，$op=1$ 表示这是一次修改操作 - 读入完成之后，交互库将调用恰好一次函数 `init` 和 $q$ 次 `modify` 或 `ask` ，用输入的数据测试你的函数。程序正常运行后会输出若干行，每行若干个数表示你对每次询问操作给出的回答；最后一行会包括两个整数 $W_1,W_2$，分别表示你程序运行消耗的总代价和单次操作消耗代价的最大值。 **下发文件中包括四组样例文件，其中第四组样例满足子任务二的特殊性质**。测试样例时请忽略输出文件最后一行的比较情况，因为交互库输出的最后一行为程序运行代价而不是询问操作的查询结果。

### 评分方式 **本题首先会受到和传统题相同的限制**。例如编译错误会导致整道题目得 $0$ 分，运行时错误、超过时间限制、超过空间限制等会导致相应测试点得 $0$ 分等。你只能访问自己定义的和交互库给出的变量及其对应的内存空间，尝试访问其他空间将可能导致编译错误或运行错误。 在上述条件基础上，在一个测试点中，若程序执行了非法的函数调用、没有正常结束运行或询问操作给出了错误回答，该测试点将会获得 $0$ 分。否则，将根据你程序消耗的代价，有两种评分方式： * 评测方式一：若 $W_1 \gt 6 \cdot 10^8$，则该测试点得 $0$ 分；否则该测试点得分为 $\frac{\frac{1.5 \cdot 10^8}{max(W_1,1.5 \cdot 10^8)} \cdot 7+3}{10} \times 该测试点所属子任务分值 $ * 评测方式二：若 $W_2 \gt 2 \cdot 10^4$，则该测试点得 $0$ 分；否则该测试点得分为 $\frac{5000}{max(W_2,5000)} \times 该测试点所属子任务分值$ 不同的子任务会使用不同的评测方式。一个子任务的得分为其中所有测试点得分的最小值。 ### 限制与约定 保证对于所有测试点均有 $1 \le n,q \le 10^5$。 | 子任务编号 | $n,q \le$ | 特殊性质 | 评测方式 | 分值 | | ---------- | --------- | -------- | -------- | ---- | | $1$ | $100$ | 无 | 一 | $10$ | | $2$ | $10^5$ | 有 | 一 | $20$ | | $3$ | $10^5$ | 有 | 二 | $20$ | | $4$ | $10^5$ | 无 | 一 | $30$ | | $5$ | $10^5$ | 无 | 二 | $20$ | 特殊性质：保证每个时刻除了 $1$ 号节点外每个节点至多只有一个儿子。 ### 后记 欣发现您五个小时还是没有做出本题，对隆的能力感到非常满意。然而第二天早上起来后，欣突然发现隆做法的复杂度证明是错的。