CF855C Helga Hufflepuff's Cup

Harry、Ron 和 Hermione 已经发现 Helga Hufflepuff 的杯子是一个魂器。通过与 Bellatrix Lestrange 的接触，Hermione 得知该杯子存放在古灵阁的 Bellatrix 家族金库中。 这个魔法银行的金库结构是一棵树形结构，总共有 $n$ 个金库，每个金库都有一个类型，编号为 $1$ 到 $m$ 之间的某个数字。树是一种无环且连通的无向图。 类型为 $k$ 的金库具有最高安全级别，所有类型为 $k$ 的金库都是最高安全级别。 最高安全级别的金库最多可以有 $x$ 个。 此外，如果某个金库是最高安全级别（金库类型为 $k$），那么与它相邻的所有金库类型都保证不是 $k$，并且它们的类型保证小于 $k$。 Harry 想要考虑所有可能的金库类型分配方案，以便能找到通往 Bellatrix 金库的最佳路线。请你告诉他，给定 Gringotts 的这棵树结构，有多少种可能的方式为每个金库分配类型，使得上述条件都被满足。

第一行输入两个用空格分隔的整数 $n$ 和 $m$，表示金库总数和可选金库类型总数。（$1 \leq n \leq 10^{5},\ 1 \leq m \leq 10^{9}$） 接下来的 $n-1$ 行，每行输入两个用空格分隔的整数 $u_i$ 和 $v_i$（$1 \leq u_i, v_i \leq n$），表示第 $i$ 条边，即存在一条路径连接金库 $u_i$ 和 $v_i$。保证给定的图是一棵树。 最后一行输入两个整数 $k$ 和 $x$（$1 \leq k \leq m,\ 1 \leq x \leq 10$），分别表示最高安全级别金库的类型及其最大数量。

输出一个整数，表示为每个金库分配类型符合条件的方案数，结果对 $10^9 + 7$ 取模。

在第 1 个测试样例中，我们不能有任何一个金库是最高安全级别的，因为其类型为 $1$，这意味着与其相邻的金库必须是类型小于 $1$ 的金库，但这是不允许的。因此，只存在一种可能的分配方式，就是所有金库都为类型 $2$。 由 ChatGPT 5 翻译