题目描述

给定一棵以 $1$ 为根的树，记点 $i$ 的颜色为 $c_i$，$m$ 次询问给出 $x,d$，表示询问以 $x$ 为根的子树下，与 $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