T363961 2023省熟中集训#1 E 独白

为了防止影响选手做题，原题目的题目背景被移除。 点击 [此处](https://www.luogu.com.cn/paste/8pnixeht) 查看。

给定一颗大小为 $n$ 的树，默认以 $1$ 为根。现在还有 $k$ 种颜色供你选择 $(1 \le k \le n)$ 。接下来有 $m$ 条询问，每条询问给定一个 $u(1 \le u \le n)$ ，你需要输出以 $u$ 为根的子树（包括点 $u$ ），给每个点染上 $k$ 种颜色的一种，有多少种合法染色方案，答案对 $10^{9}+7$ 取模。 当然如果没有任何其他条件的话，答案显然为 $k^{size} \mod (10^{9}+7)$ 。这实在是太简单了，所以每个节点会有一个属性 $c_i(1 \le c_i \le n )$ ，相同属性的点染的颜色应当相同，但不保证 $c_i$ 互不相同。同时，给出 $d$ 条限制关系，每条限制关系给定一个 $x_i,y_i(1 \le x_i,y_i \le n)$ ，代表属性为 $x_i$ 的点要和属性为 $y_i$ 的点颜色相同，反之亦然。

第一行两个整数 $n,k$ ，代表树的大小，颜色数。 接下来一行 $n$ 个整数，第 $i$ 个数表示点 $i$ 的属性。 接下来一行一个整数 $d$ ，代表限制数。 接下来 $d$ 行，每行两个整数 $x_i,y_i$ ，代表属性为 $x_i$ 的点与属性为 $y_i$ 的点的颜色必须相同。 接下来 $n-1$ 行，每行给定两个整数 $x,y$ ，代表 $x,y$ 之间有一条边，数据保证输入的图构成一颗树。 接下来一行一个整数$m$，代表询问数。 接下来$m$行，每行$1$个整数，代表询问的根$u$。

共 $m$ 行。对于一个根为 $u$ 的询问，输出对应的方案数。

### 样例说明： 输入的树构成一条 $1->2->3$ 的链，属性依次为$1，2，3$，有 $3$ 种颜色 因为属性为 $1$ 的点必须和属性为 $3$ 的点染同样的颜色，所以对于以 $1$ 为根的子树而言，有 $3 \times 3=9$ 种染色方法，对于以 $2$ 为根的子树而言，同样也有 $3 \times 3=9$ 种染色方法，对于以 $3$ 为根的子树，只有一个节点，有 $3$ 种颜色可选，那么答案自然是 $3$ 种。 ### 数据范围： 对于10%的数据，$1 \le n \le 10^{3},d=0$； 另有30%的数据，$d=0$； 对于全部数据，$1 \le k,d \le n \le 10^{6},1 \le m \le 10^{6}$。 **由于输入数据过大，请使用较快的I/O方式（如scanf等）。** 注：本题idea来自于CFM妹妹QwQ