#P4771. 七彩树

    ID: 3889 传统题 5000ms 256MiB 尝试: 2666 已通过: 426 难度: 8 上传者: 标签>CF2500提高+/省选-差分转化子树转区间LCA树上倍增有序集合可持久化线段树路径复制历史版本查询

七彩树

题目描述

给定一棵以 11 为根的树,记点 ii 的颜色为 cic_i,mm 次询问给出 x,dx,d,表示询问以 xx 为根的子树下,与 xx 深度不超过 dd 的所有节点中有多少种不同的颜色。

输入格式

第一行包含一个正整数 TT,表示测试数据的组数。

每组数据中,第一行包含两个正整数 nn 和 mm,表示节点数和询问数。

第二行包含 nn 个正整数,其中第 ii 个数为 cic_i,分别表示每个节点的颜色。

第三行包含 n−1n-1 个正整数,其中第 ii 个数为 fi+1f_{i+1},表示节点 i+1i+1 的父亲节点的编号。

接下来 mm 行,每行两个整数 xx 和 dd,依次表示每个询问。

输入数据经过了加密,对于每个询问,如果你读入了 xx 和 dd,那么真实的 xx 和 dd 分别是 xxor⁡lastx \operatorname{xor} last 和 dxor⁡lastd\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\% 的数据,1≤T≤5001\le T \le 500,1≤n,m≤1051\le n,m\le 10^5,1≤x,ci≤n1\le x,c_i \le n,0≤d<n0\le d < n,∑(n+m)≤5×105\sum(n+m)\le 5\times 10^5,1≤fi<i1\le f_i < i。

题目来源

By Claris