P8262 [CTS2022] WBTT

**这是一道交互题。** #### 本地测试需 #include #### 提交时请采用以下模板，而不 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,vectordad,vectorve); 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$ 的大小按照一定方式给分。

无

无

### 评分方式 **本题首先会受到和传统题相同的限制**。例如编译错误会导致整道题目得 $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$ 号节点外每个节点至多只有一个儿子。 ### 后记 欣发现您五个小时还是没有做出本题，对隆的能力感到非常满意。然而第二天早上起来后，欣突然发现隆做法的复杂度证明是错的。