#R1016. 七彩树
七彩树
题目描述
给定一棵 个点的有根树,编号依次为 到 ,其中 号点是根节点。每个节点都被染上了某一种颜色,其中第 个节点的颜色为 。如果 ,那么我们认为点 和点 拥有相同的颜色。定义 为 节点与根节点的距离,为了方便起见,你可以认为树上相邻的两个点之间的距离为 。站在这棵色彩斑斓的树前面,你将面临 个问题。每个问题包含两个整数 和 ,表示询问 子树里且 不超过 的所有点中出现了多少种本质不同的颜色。请写一个程序,快速回答这些询问。
输入格式
第一行包含一个正整数 ,表示测试数据的组数。
每组数据中,第一行包含两个正整数 和 ,表示节点数和询问数。
第二行包含 个正整数,其中第 个数为 ,分别表示每个节点的颜色。
第三行包含 个正整数,其中第 个数为 ,表示节点 的父亲节点的编号。
接下来 行,每行两个整数 和 ,依次表示每个询问。
输入数据经过了加密,对于每个询问,如果你读入了 和 ,那么真实的 和 分别是 和 ,其中 表示这组数据中上一次询问的答案,如果这是当前数据的第一组询问,那么 。
输出格式
对于每个询问输出一行一个整数,即答案。
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
数据规模与约定
对于 的数据,,,,,,。