题目描述

给定一棵 $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 \oplus last$ 和 $d \oplus last$，其中 $last$ 表示该组数据中上一次询问的答案，如果这是当前数据的第一组询问，那么 $last = 0$。

输出格式

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

输入数据 1

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

1
2
3
1
1
2
1
1

数据规模与约定

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

题目来源

BZOJ4771