题目背景

伟大的科学家欣准备建造强人工智能隆统治世界。在输入一些越南的算法竞赛题作为训练集后，她发现隆自动生成了一个新的问题，并给出了一份解答。同时隆还将测试集中 30% 的输入数据归约到了这个问题。

欣连忙将这个问题抄录如下：给定一棵有根树，你需要支持两种操作：

• 查询树链元素和；
• 将一个点的父亲改成另一个点。

“这个问题并不强啊，为什么能解决测试集中 30% 的问题呢？”欣心里想。

在关闭训练结果页面前，欣突然发现，隆给出的这个问题中，信息合并的代价并不是 $O(1)$ 的。

欣陷入了沉思，发现自己并不会这道题。为了知道这题有多难，欣将这题放到了您的面前。

题目描述

你需要维护一棵以 $1$ 为根的有根树。这棵树有 $n$ 个点。初始时对于所有 $2 \le i \le n$，点 $i$ 有一个父亲 $p_i$，保证 $p_i<i$。

一开始你有 $n$ 个集合 $\{1\},\{2\},\cdots,\{n\}$。对于任意两个集合 $A$ 和 $B$，如果 $A\cap B=\varnothing$，那么你可以通过一次操作，消耗 $|A|+|B|$ 的代价，获得集合 $A\cup B$。

之后有 $q$ 次操作。每次操作有两种类型：

• 0 a b：记树上 $a$ 到 $b$ 之间的路径上的点构成的点集为 $S$。你需要将 $S$ 表示为 $\bigcup_{i=1}^{k} A_i$，需要满足 $A_i$ 是你已经获得的集合，且对于任意 $i\ne j$，有 $A_i\cap A_j=\varnothing$。用 $(A_1,A_2,\cdots,A_k)$ 回答一次询问的代价为 $k$。
• 1 a b：表示将点 $a$ 的父亲改为 $b$，保证 $a>1$，且修改后这 $n$ 个点仍构成一棵树，但不保证 $a>b$。你可以在这次操作中新生成一些集合，用以应对之后的询问。

记你整个程序运行过程中消耗的总代价为 $C_1$，单次操作消耗代价最大值为 $C_2$。每个子任务会根据 $C_1,C_2$ 的大小按照一定方式给分。

提交方式

本题在 Hydro OJ 中配置为提交函数题。

你不需要，也不应该实现 main 函数；不需要从标准输入读取数据；不需要向标准输出输出内容。

你需要提交一个 C++ 源文件，并包含头文件：

#include "long.h"

你需要实现如下三个函数：

void init(int id, int n, int q, std::vector<int> dad, std::vector<infoset> ve);
void modify(int x, int y);
void ask(int x, int y);

评测程序会先调用一次 init，然后按照测试数据依次调用 modify 或 ask，共调用 $q$ 次。

请注意：

• 不要定义 main 函数；
• 不要自行读入输入；
• 不要输出调试信息；
• 系统会自动提供隐藏的 long.h 和评测入口；
• 你只需要实现上述三个函数。

接口说明

Hydro 评测时会提供头文件 long.h。本包中的评测接口采用集合哈希表示 infoset，其核心定义如下：

struct sethash {
    int val;
    void encode();
    void decode();
    void operator=(int x);
};

struct infoset {
    sethash sum;
    int sz;
    int size() const { return sz; }
};

其中：

• sum 表示集合中所有元素对应哈希值之和；
• sz 表示集合大小；
• encode() / decode() 用于在内部编码值与真实哈希值之间转换；
• size() 返回集合大小。

头文件还提供了表示空集的常量：

const infoset emptyset;

此外，你可以调用如下函数：

infoset merge(const infoset &A, const infoset &B);

含义：

• 以一定代价生成一个新集合 $A\cup B$；
• 调用该函数要求 $A\cap B=\varnothing$；
• 你可以多次重复生成同一个集合，但每次都会计入代价。

你还可以调用：

void report(infoset A);

含义：

• 该函数只能在处理询问 ask 的过程中调用；
• 表示你需要消耗 $1$ 的代价，将集合 $A$ 加入本次询问的回答中；
• 在本 Hydro 配置中，评测程序会根据 A.sum 和 A.sz 对回答进行校验。

因此，除了通过 merge 得到集合外，也可以在确保哈希值与集合大小正确的前提下构造 infoset 并调用 report。

函数说明

init

void init(int id, int n, int q, std::vector<int> dad, std::vector<infoset> ve);

该函数会在所有操作开始前被调用一次。你可以在其中进行预处理。

参数含义：

• id：当前测试点所属子任务编号；
• n：点数；
• q：操作数；
• dad：长度为 $n-1$，其中 dad[i] 表示初始时点 $i+2$ 的父亲；
• ve：长度为 $n$，其中 ve[i] 表示初始集合 $\{i+1\}$。

在 init 中消耗的代价不会计入单次操作消耗代价最大值，但会计入整个程序运行过程中消耗的总代价。

modify

void modify(int x, int y);

执行一次修改操作，将点 $x$ 的父亲改为点 $y$。

保证 $x>1$，且修改后仍然是一棵以 $1$ 为根的树。

ask

void ask(int x, int y);

执行一次查询操作，询问 $x$ 到 $y$ 的树链点集。

你需要在该函数中调用若干次 report 来回答询问。本次询问结束时，评测程序会检查你汇报的所有集合是否满足条件。

输入格式

本题为提交函数题，选手程序不需要从标准输入读取数据。

所有输入数据均由评测程序传入 init、modify 和 ask 函数。

输出格式

本题为提交函数题，选手程序不需要向标准输出输出内容。

你只需要在 ask 函数中通过调用 report 汇报答案。

评分方式

本题首先会受到和传统题相同的限制。例如，编译错误会导致整道题目得 $0$ 分；运行时错误、超过时间限制、超过空间限制等会导致相应测试点得 $0$ 分。

在上述条件基础上，在一个测试点中，若程序执行了非法的函数调用、没有正常结束运行或询问操作给出了错误回答，该测试点将获得 $0$ 分。否则，将根据你程序消耗的代价给分。

有两种评分方式：

• 评测方式一：主要根据总代价 $C_1$ 给分；
• 评测方式二：主要根据单次操作最大代价 $C_2$ 给分。

具体评分由评测程序和特殊检查器完成。

限制与约定

保证对于所有测试点均有：

$$1 \le n,q \le 10^5$$

子任务编号	$n,q\le$	特殊性质	评测方式	分值
$1$	$100$	无	一	$10$
$2$	$10^5$	有		$20$
$3$			二
$4$		无	一	$30$
$5$			二	$20$

特殊性质：保证每个时刻除了 $1$ 号节点外，每个节点至多只有一个儿子。

样例与本地测试说明

原始下发文件中包含若干本地测试辅助文件，例如公开版 long.h、grader.cpp 和样例数据。这些文件仅供理解原题接口与本地调试参考。

请注意：公开版 additional_file/long.h 使用 vector<int> 模拟集合；Hydro 隐藏评测使用 testdata/long.h 中的哈希型 infoset。二者实现不同，但函数入口均为 init、modify、ask。

在 Hydro OJ 上提交时，请以本题页面中的提交函数说明为准：提交代码只需要包含 long.h 并实现 init、modify、ask 三个函数。

后记

欣发现您五个小时还是没有做出本题，对隆的能力感到非常满意。然而第二天早上起来后，欣突然发现隆做法的复杂度证明是错的。