树上数颜色

• 时间限制：3 秒
• 内存限制：512 MiB

题目描述

给定一棵以结点 $1$ 为根的树，每个结点都有一种颜色。

每次询问给出一个结点 $x$，请计算以 $x$ 为根的子树中共有多少种不同的颜色。

输入格式

第一行输入一个整数 $n$，表示树的结点数。

接下来 $n-1$ 行，每行输入两个整数 $u,v$，表示结点 $u$ 与结点 $v$ 之间有一条边。

接下来一行输入 $n$ 个整数 $c_1,c_2,\ldots,c_n$，其中 $c_i$ 表示结点 $i$ 的颜色。

接下来一行输入一个整数 $m$，表示询问数。

接下来 $m$ 行，每行输入一个整数 $x$，表示询问以 $x$ 为根的子树。

输出格式

对每次询问输出一行一个整数，表示相应子树中的不同颜色数。

样例输入 1

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

样例输出 1

3
2
1
1
1

数据范围

对于所有数据，保证 $1\le n\le 10^5$，$0\le m\le n$，$0\le c_i\le n$，输入的边构成一棵树，$1\le x\le n$。