提示

这不是普通输入输出题。若配置到 Hydro，应作为“提交函数题”处理：选手实现 solve，不写 main，由 grader.cpp 负责读入和输出。题面应在开头明确这一点。

题目描述

一天早上，Egor 走到外面，看见沥青地上画着经典的跳房子方格：一共有 $n$ 个方格，每个方格里写着一些数字，第 $i$ 个方格里写着数字 $a_i$。不过这些并不是普通方格，每个方格还与一些其他方格相连。

跳房子游戏从某个方格开始，每次跳到一个与当前方格相连的方格，并且不能重复跳到同一个方格。游戏可以在任意时刻结束。访问过的方格序列

$$v_0,v_1,\ldots,v_{k-1}$$

称为一次跳跃序列。

地上的方格连接关系构成一棵树，因此任意两个方格之间只有唯一一条路径。

跳跃序列的“酷炫度”定义为满足

$$a_{v_i}=i$$

的下标 $i$ 的数量。

Egor 想知道对于一些方格对 $u,v$，从 $v_0=u$ 跳到 $v_{k-1}=v$ 的跳跃序列有多酷，以判断是否值得这么跳。

不过 Egor 经常被打断。因此他有时会擦掉第 $s$ 个方格中的数字，并写上一个新数字 $x$。由于数数对 Egor 来说很困难，他向你寻求帮助。

接下来的 $q$ 分钟中，你需要帮助 Egor 回答关于跳跃酷炫度的问题。第 $i$ 分钟，Egor 会进行以下两种操作之一：

1. 擦掉方格 $s$ 中的数字，并写入数字 $x$；
2. 询问从方格 $u$ 到方格 $v$ 的跳跃序列酷炫度。

你需要回答 Egor 的每个询问。

提交格式

这是一个非传统题，采用 grader 测试格式。你只需要在提交文件中实现函数 solve。该函数会由评测程序调用，函数返回值会作为本题答案。

也就是说，提交代码中不应进行输入输出。如果使用 C++，代码中不能包含 main 函数。可以实现任意数量的辅助函数、结构体、类和全局变量，但全部解题代码必须在一个文件中。

C++ 需要实现如下函数：

std::vector<int> solve(
    int n,
    int q,
    std::vector<int> a,
    std::vector<int> p,
    std::vector<int> qt,
    std::vector<int> qx,
    std::vector<int> qy
);

Python3 或 PyPy3 需要实现如下函数：

def solve(n, q, a, p, qt, qx, qy):

其中 $n,q$ 为整数；$a,p$ 为长度为 $n$ 的整数列表；$qt,qx,qy$ 为长度为 $q$ 的整数列表。

注意，原题不保证 Python3 或 PyPy3 可以获得满分。

函数参数含义如下：

• $n$（$1\le n\le 10^6$）：方格数量。
• $q$（$1\le q\le 10^6$）：询问数量。
• $a$（$0\le a[i]\le n$）：长度为 $n$ 的数组，表示方格中初始写着的数字。
• $p$（$-1\le p[i]<n$）：长度为 $n$ 的数组。若把跳房子方格看作一棵有根树，$p[i]$ 表示方格 $i$ 的父亲；根节点的 $p[i]$ 为 $-1$。保证该数组定义了一棵合法的树。
• $qt$（$1\le qt[i]\le 2$）：长度为 $q$ 的数组，表示询问类型。
• $qx,qy$：定义询问内容的数组。

对于每个 $0\le i<q$，第 $i$ 个询问如下：

• 如果 $qt[i]=1$，则表示擦掉编号为 $qx[i]$ 的方格中的数字，并写入 $qy[i]$。此时满足 $0\le qx[i]<n$，$0\le qy[i]\le n$。
• 如果 $qt[i]=2$，则表示询问从方格 $qx[i]$ 到方格 $qy[i]$ 的跳跃序列酷炫度。此时满足 $0\le qx[i],qy[i]<n$。

所有方格和询问均从 $0$ 开始编号。

函数 solve 返回一个整数数组，包含所有第二类询问的答案。数组长度应等于第二类询问数量。C++ 中返回类型为 vector<int>，Python3 中返回列表。

保证程序执行过程中 solve 恰好被调用一次。

本地测试说明

原题提供模板文件 tree.cpp 与 tree.py。对于 C++，还提供头文件 tree.h，其中包含函数 solve 的定义。

同时提供 grader 文件 grader.cpp 和 grader.py，其中实现了从标准输入读入数据、调用 solve、输出返回值。在正式评测系统中，grader 文件可能不同。

若要编译写在 tree.cpp 中的 C++ 代码，可使用：

g++ -std=c++20 grader.cpp tree.cpp -o grader

运行后会生成名为 grader 或 grader.exe 的可执行文件。

如果直接复制 grader 中的输入输出代码到自己的文件中用于本地测试，正式提交前必须删去这些输入输出实现，尤其是 C++ 中的 main 函数。

Grader 输入格式

提供的 grader 按如下格式读取测试数据。

第一行包含两个整数 $n,q$（$1\le n,q\le 10^6$），表示跳房子方格数量和 Egor 的操作数量。

第二行包含 $n$ 个整数 $a_0,a_1,\ldots,a_{n-1}$（$0\le a_i\le n$），表示方格中的初始数字。

第三行包含 $n$ 个整数 $p_0,p_1,\ldots,p_{n-1}$（$-1\le p_i<n$），表示树中每个节点的父亲。若 $p_i=-1$，则节点 $i$ 是根；否则 $p_i$ 是节点 $i$ 的父亲。保证该父亲数组形成一棵合法有根树。

接下来 $q$ 行描述询问。对于任意 $0\le i<q$，第 $i$ 个询问根据类型按如下格式给出：

• 1 s x（$0\le s<n$，$0\le x\le n$）：Egor 擦掉方格 $s$ 中的数字并写入 $x$。在 solve 参数中，满足 $qt[i]=1,qx[i]=s,qy[i]=x$。
• 2 u v（$0\le u,v<n$）：Egor 询问从 $u$ 到 $v$ 的跳跃序列酷炫度。 在 solve 参数中，满足 $qt[i]=2,qx[i]=u,qy[i]=v$。

Grader 输出格式

grader 输出函数 solve 的结果，即所有第二类询问的答案。

样例 1

4 3
1 1 2 2
-1 0 0 2
2 0 3
1 2 1
2 0 3

1
2

样例 2

5 5
0 1 2 3 4
1 2 -1 2 3
2 0 4
1 0 1
1 1 0
2 0 4
2 1 0

5
3
2

样例解释

在样例中，输入输出为 grader 使用的数据格式。

第一个样例中的树形结构如下：

以 $0$ 为根，$1$ 与 $2$ 为 $0$ 的儿子，$3$ 为 $2$ 的儿子。

对于第一个询问，考虑从 $0$ 到 $3$ 的跳跃序列：

1. $v_0=0$，$a_0=1\ne 0$，因此该方格不增加酷炫度。
2. $v_1=2$，$a_2=2\ne 1$，因此也不增加酷炫度。
3. $v_2=3$，$a_3=2=2$，该跳跃是酷炫的。

因此第一个询问的酷炫度为 $1$。

第二个询问后，方格 $2$ 中的数字变为 $1$。因此第二次询问中，跳到方格 $2$ 也变得酷炫，答案变为 $2$。

评分方式

本题测试点由 14 个分组组成。只有通过某一组及其要求的部分前置分组时，才能获得该组分数。注意，部分分组不要求通过样例。Offline-testing 表示该组测试结果只会在比赛结束后给出。

设 $c_i$ 为与第 $i$ 个方格相连的方格数量。

组别	分数	附加限制：$n$	附加限制：$q$	依赖分组	说明
0		-			样例
1	10	$n\le 1000$	$q\le 1000$	0	-
2	11	$n\le 200000$	$q\le 5000$	0,1
3	14		$q\le 200000$	-	没有第一类询问
4	5				恰有一个方格满足 $c_i=2$，其他方格满足 $c_i\le 3$
5	11				$c_i\le 2$
6	10				所有第二类询问均满足 $v_i=0$
7	9	$n\le 100000$	$q\le 100000$	0,1	-
8		$n\le 200000$	$q\le 200000$	0–7
9	17	$n\le 500000$	$q\le 500000$	0–8
10	1	$n\le 600000$	$q\le 600000$	0–9	Offline-testing
11		$n\le 700000$	$q\le 700000$	0–10
12		$n\le 800000$	$q\le 800000$	0–11
13		$n\le 900000$	$q\le 900000$	0–12
14		-		0–13