#1731. BZOJ 4771. 七彩树

BZOJ 4771. 七彩树

题目描述

给定一棵 nn 个点的有根树,编号依次为 11nn,其中 11 号点是根节点。每个节点都被染上了某一种颜色,其中第 ii 个节点的颜色为 cic_i。如果 ci=cjc_i=c_j,那么我们认为点 ii 和点 jj 拥有相同的颜色。定义 depthidepth_iii 节点与根节点的距离,为了方便起见,你可以认为树上相邻的两个点之间的距离为 11。站在这棵色彩斑斓的树前面,你将面临 mm 个问题。每个问题包含两个整数 xxdd,表示询问 xx 子树里且 depthdepth 不超过 depthx+ddepth_x+d 的所有点中出现了多少种本质不同的颜色。请写一个程序,快速回答这些询问。

输入格式

第一行包含一个正整数 TT,表示测试数据的组数。 每组数据中,第一行包含两个正整数 nnmm,表示节点数和询问数。 第二行包含 nn 个正整数,其中第 ii 个数为 cic_i,分别表示每个节点的颜色。 第三行包含 n1n-1 个正整数,其中第 ii 个数为 fi+1f_{i+1},表示节点 i+1i+1 的父亲节点的编号。 接下来 mm 行,每行两个整数 xxdd,依次表示每个询问。

输入数据经过了加密,对于每个询问,如果你读入了 xxdd,那么真实的 xxdd 分别是 xxorlastx \operatorname{xor} lastdxorlastd\operatorname{xor} last,其中 lastlast 表示这组数据中上一次询问的答案,如果这是当前数据的第一组询问,那么 last=0last=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%100\% 的数据,1T5001\le T \le 5001n,m1051\le n,m\le 10^51x,cin1\le x,c_i \le n0d<n0\le d < n(n+m)5×105\sum(n+m)\le 5\times 10^51fi<i1\le f_i < i

题目来源

By Claris