题目描述

给定一棵 $n$ 个点的无根树，树上每个点有一种颜色。进行 $q$ 次询问：对某个点 $x$，询问与 $x$ 距离不超过 $d$ 的所有点中，出现过的颜色有多少种。

一个测试点中有多组测试数据。

输入格式

第一行一个整数 $num$，表示该测试点编号；若为样例则该数为 $0$。
第二行一个整数 $T$，表示测试数据组数。

对于每组数据：

• 第一行一个整数 $n$，表示树的大小。
• 接下来一行 $n$ 个整数，第 $i$ 个整数 $c_i$ 表示第 $i$ 个节点的颜色。
• 接下来 $n-1$ 行每行两个整数 $u,v$，表示树上的一条边 $(u,v)$。
• 接下来一个整数 $q$，表示询问个数。
• 接下来 $q$ 行每行两个整数 $x,d$，表示询问树上与 $x$ 距离 $\le d$ 的范围内出现过的颜色种数。

输出格式

对于每组数据输出 $q$ 行，每行一个整数，表示每个询问的答案。

0
1
5
1 2 3 1 2
1 2
1 3
2 4
2 5
5
1 1
2 0
3 1
4 2
3 2

3
1
2
2
3

数据范围与提示

• 对于所有数据：$n,q\le 10^5$，$1\le c_i,u_i,v_i,x\le n$，$0\le d\le n$，$1\le T\le 3$。
• 对于测试点 $1\sim 4$：$n,q\le 5000$。
• 对于测试点 $5\sim 8$：$u_i=1$。
• 对于测试点 $9\sim 13$：$u_i=i,\ v_i=i+1$。
• 对于测试点 $14\sim 18$：$c_i=i$。
• 对于测试点 $19\sim 25$：无特殊限制。