题目描述

给定一棵 $n$ 个点的有根树，编号依次为 $1$ 到 $n$，其中 $1$ 号点是根节点。每个节点都被染上了某一种颜色，其中第 $i$ 个节点的颜色为 $c_i$。如果 $c_i=c_j$，那么我们认为点 $i$ 和点 $j$ 拥有相同的颜色。定义 $depth_i$ 为 $i$ 节点与根节点的距离，为了方便起见，你可以认为树上相邻的两个点之间的距离为 $1$。站在这棵色彩斑斓的树前面，你将面临 $m$ 个问题。每个问题包含两个整数 $x$ 和 $d$，表示询问 $x$ 子树里且 $depth$ 不超过 $depth_x+d$ 的所有点中出现了多少种本质不同的颜色。请写一个程序，快速回答这些询问。

输入格式

第一行包含一个正整数 $T$，表示测试数据的组数。 每组数据中，第一行包含两个正整数 $n$ 和 $m$，表示节点数和询问数。 第二行包含 $n$ 个正整数，其中第 $i$ 个数为 $c_i$，分别表示每个节点的颜色。 第三行包含 $n-1$ 个正整数，其中第 $i$ 个数为 $f_{i+1}$，表示节点 $i+1$ 的父亲节点的编号。 接下来 $m$ 行，每行两个整数 $x$ 和 $d$，依次表示每个询问。

输入数据经过了加密，对于每个询问，如果你读入了 $x$ 和 $d$，那么真实的 $x$ 和 $d$ 分别是 $x \operatorname{xor} last$ 和 $d\operatorname{xor} last$，其中 $last$ 表示这组数据中上一次询问的答案，如果这是当前数据的第一组询问，那么 $last=0$。

输出格式

对于每个询问输出一行一个整数，即答案。

1
5 8
1 3 3 2 2
1 1 3 3
1 0
0 0
3 0
1 3
2 1
2 0
6 2
4 1

1
2
3
1
1
2
1
1

数据规模与约定

对于 $100\%$ 的数据，$1\le T \le 500$，$1\le n,m\le 10^5$，$1\le x,c_i \le n$，$0\le d < n$，$\sum(n+m)\le 5\times 10^5$，$1\le f_i < i$。

题目来源

By Claris