给定一棵 $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
,意义如上述。
输出格式
对每个 $2$ 操作,输出一行一个数表示答案。
样例数据
样例 1 输入
4 5 1 1 2 3 1 1 1 2 4 1 1 1 1 4 3 2 4 1 3 3
样例 1 输出
2 4
子任务
Idea:nzhtl1477,Solution:nzhtl1477,Code:ccz181078,Data:ccz181078
对于 $20\%$ 的数据,满足 $n,m\leq2\times 10^3$。
对于 $40\%$ 的数据,满足 $n,m\leq2\times 10^5$。
对于另外 $30\%$ 的数据,满足 $1\le a_i,y\le 2$。
对于 $100\%$ 的数据,满足 $1\le n,m,a_i,x,y\le10^6$。