P16035 [CSPro 33] 文件夹合并

洛谷的测试数据仅供民间交流使用，非官方测试数据。官方评测链接：。

新入职西西艾弗岛有限公司的小 C 接替了刚刚升职的小 S 的项目。然而小 C 打开项目工程时，一层层嵌套的文件夹让小 C 感到眼花缭乱。为了精简项目结构，小 C 决定对项目的文件夹进行一些必要的合并。 项目中共有 $n$ 个文件夹。为了方便，我们用 $1$ 至 $n$ 的整数给这 $n$ 个文件夹编号，其中编号为 $1$ 的文件夹为项目的根文件夹，其他每个文件夹都有一个父文件夹，这些文件夹构成了树形结构。除了子文件夹以外，第 $i$ 个文件夹内还直接存储了 $d_i$ 字节的数据。 小 C 进行了若干次文件夹合并操作。每次操作中小 C 会选择一个文件夹 $x_j$，将这个文件夹和它的所有子文件夹合并。具体地，小 C 会进行以下操作：遍历 $x_j$ 的子文件夹 $y$，将文件夹 $y$ 包含的所有文件夹和文件移动到文件夹 $x_j$，然后删除文件夹 $y$。所有文件和文件夹的名称是两两不同的，合并过程中不需要考虑文件或文件夹重名的情况。在每一次合并操作后，小 C 需要知道文件夹 $x_j$ 内共有几个文件夹以及多少字节的数据。 例如，考虑以下项目：根文件夹内有文件夹 $2$ 和文件夹 $3$ 以及 $100$ 字节数据，其中文件夹 $2$ 为空文件夹，文件夹 $3$ 内有 $200$ 字节数据和文件夹 $4$，文件夹 $4$ 包含 $300$ 字节数据。对根文件夹进行一次合并后，文件夹 $2$ 和文件夹 $3$ 被合并至根文件夹，此时根文件夹下有文件夹 $4$ 以及 $300$ 字节数据，而文件夹 $4$ 下也包含 $300$ 字节数据。 在合并文件夹的过程中，小 C 常常需要访问某个文件夹 $z_j$ 下的文件。此时，小 C 会从根文件夹开始，每次进入当前文件夹的一个子文件夹。小 C 需要知道按照以上过程，获取到文件夹 $z_j$ 下的文件至少需要经过多少个文件夹。 例如，在以上项目中，未对根文件夹进行合并前，访问根文件夹下的文件只需要经过根文件夹一个文件夹，而访问文件夹 $4$ 则需要经过根文件夹以及文件夹 $3$ 和 $4$。而对根文件夹进行合并之后，访问文件夹 $4$ 只需要经过根文件夹和文件夹 $4$ 了。 在整个项目中，小 C 一共进行了 $m$ 次文件夹合并以及文件访问操作。你需要帮助小 C 正确维护文件夹之间的关系，并在每次操作后正确回答小 C 需要的数据。

从标准输入读入数据。 输入的第一行两个整数 $n, m$，分别表示文件夹数量以及操作次数。 第二行 $(n - 1)$ 个整数 $f_2, \cdots , f_n$，其中 $f_i$ 表示文件夹 $i$ 的父文件夹编号。 第三行 $n$ 个整数 $d_1, d_2, \cdots , d_n$，其中 $d_i$ 表示文件夹 $i$ 中数据的存储量。 接下来 $m$ 行第 $j$ 行两个整数，第一个整数 $op_j$ 表示操作类型。若 $op_j = 1$ 则表示一次文件夹合并操作，接下来一个整数 $x_j$ 表示合并的文件夹编号；若 $op_j = 2$ 则表示一次文件访问操作，接下来一个整数 $z_j$ 表示访问的文件夹编号。

输出到标准输出。 输出 $m$ 行，第 $j$ 行表示第 $j$ 个操作中小 C 需要的数据：若 $op_j = 1$ 则输出两个整数，依次表示文件夹 $x_j$ 的子文件夹数量以及数据的存储量；若 $op_j = 2$ 则输出一个整数表示小 C 获取文件夹 $z_j$ 下的数据最少需要经过的文件夹个数。

### 子任务 对于所有测试数据， - $1 \le n \le 5 \times 10^5, 1 \le m \le 3 \times n$, - $1 \le f_i \le n$，输入的文件夹结构构成树形结构， - $0 \le d_i \le 10^5$, - $1 \le x_j, z_j \le n$，每次合并操作中给出的文件夹 $x_j$ 没有被删除，每次文件访问操作中给出的文件夹 $z_j$ 没有被删除。 | 子任务编号 | $n \le$ | 特殊性质 | 分值 | |:----------:|:-----------:|:--------:|:----:| | 1 | 500 | 无 | 10 | | 2 | 5,000 | ^ | 15 | | 3 | $10^5$ | ^ | ^ | | 4 | $5 \times 10^5$ | A | 5 | | 5 | ^ | B | ^ | | 6 | ^ | C | 10 | | 7 | ^ | D | 15 | | 8 | ^ | E | 10 | | 9 | ^ | 无 | 15 | 特殊性质 A：$f_i = (i - 1)$。 特殊性质 B：$f_i = 1$。 特殊性质 C：在文件夹合并操作中，$x_j = 1$。 特殊性质 D：$op_j = 1$，即没有文件访问操作。 特殊性质 E：$op_j = 2$，即没有文件夹合并操作。