You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

问题描述

在这个问题中，我们给定一棵树，树上的每个节点都有一个权重。对于每个节点，如果以该节点为根的子树中恰好出现 $k$ 次的权重种类数，我们定义该节点的值为这个数目。

我们需要对每个节点计算其值。

输入格式

输入的第一行包含一个整数 $T$（$T \le 20$），表示测试用例的数量。

对于每个测试用例：

• 第一行包含两个整数 $n$（$n \le 100000,k \le 100000$），表示树中的节点数和出现的次数。
• 第二行包含 $n$ 个整数 $v_1, v_2, ..., v_n$（$0 \le v_i \le 10^9$），表示每个节点的权重。
• 接下来的 $n-1$ 行，每行包含两个整数 $u$ 和 $v$，表示节点 $u$ 和节点 $v$ 之间有一条边。
• 接下来一行包含一个整数 $q$（$q \le 100000$），表示查询的数量。
• 接下来的 $q$ 行，每行包含一个整数 $u$，表示查询以节点 $u$ 为根的子树的值。

输出格式

对于每个测试用例：

• 首先输出一行 "Case #i:"，其中 $i$ 表示测试用例编号（从 1 开始）。
• 然后对于每个查询，输出一个整数，表示对应节点的值。

1
3 1
1 2 2
1 2
1 3
3
2
1
3

Case #1:
1
1
1