D-石老板魂飞魄散_第二届天元编程邀请赛（提高组）

石老板魂飞魄散

比赛主页

时间限制：C/C++/Rust/Pascal 4秒，其他语言8秒
空间限制：C/C++/Rust/Pascal 512 M，其他语言1024 M
64bit IO Format: %lld

题目描述

由于上题做的太慢，石老板没有得到及时的抢救，现在他的魂来找你复仇了......

给定一棵 $n$ 个节点的树，第 $i$ 个点有点权 $a_i$ 。

定义一个点 $x$ 所在的极大同色连通块为一个极大的点集 $S$ ，满足 $x\in S$ ，且对任意点集中的元素 $i,j$ ，可以找到一个节点序列 $p_1,p_2,...p_t$ ，满足 $p_1=i$ ， $p_t=j$ ，且对任意 $k$ 为 $[1,t)$ 中的整数，满足 $p_k$ 与 $p_{k+1}$ 在树上相邻，且 $a_{p_k}=a_{p_{k+1}}$ ，且 $p_k\in S$ 。

有 $m$ 次操作：

1 x y：给出一个点 $x$ ，将其所在的极大同色连通块中每个点的点权修改为 $y$ 。

2 x：给出一个点 $x$ ，查询其所在的极大同色连通块的大小

输入描述:

第一行两个数 $n,m$ 。

第二行 $n-1$ 个数，第 $i$ 个数表示树上第 $i+1$ 的节点的父亲节点的编号，保证父亲节点的编号比该节点小。

第三行 $n$ 个数，第 $i$ 个数表示 $a_i$ 。

之后 $m$ 行，每行形如 1 x y 或 2 x，意义如上述。

输出描述:

对每个  操作，输出一行一个数表示答案。

示例1

输入

复制

输出

复制

2
4

备注:

大样例链接: https://pan.baidu.com/s/1uR8keXNeZmYLN46rMZ0Mfg 密码: a3tl

ex_test2.in/ex_test2.ans 对应下面 $20\%$ 数据的部分。

ex_test3.in/ex_test3.ans 对应下面 $100\%$ 数据的部分。

对于前 $20 \%$ 的数据，保证 $n,m \leq 1000$ 。

对于前 $40 \%$ 的数据，保证 $n,m \leq 100000$ 。

对于另外 $30\%$ 的数据，保证 $1\le a_i\le 2$ 。

对于 $100\%$ 的数据，满足 $1\le n,m\leq 10^6$ ， $1\le a_i\le n$ 。