P13484 [GCJ 2008 EMEA SemiFinal] Rainbow Trees

在图论中，树是一个连通、无向、无环的简单图。一个有 $n$ 个节点的树总是有 $n - 1$ 条边。 树中的一条路径是由一系列互不相同且相连的边组成的（路径中每对相邻的边共享一个顶点）。 考虑一棵有 $n$ 个顶点和 $n - 1$ 条边的树。你可以用 $k$ 种颜色中的任意一种来给每条边染色。 如果对边的染色满足：在树中任意长度为 $2$ 或 $3$ 的路径上，所有边的颜色都不同（即任意两条相邻的边颜色不同，任意三条连续的边颜色也都不同），则称这种染色为“彩虹染色”。 给定一棵树和颜色数 $k$，请你计算有多少种不同的彩虹染色方案。答案对 $1000000009$ 取模。

输入的第一行是测试用例的数量 $C$。对于每个测试用例，包含如下内容： - 第一行包含两个整数，格式为“$n$ $k$”。$n$ 表示树的节点数，$k$ 表示可用的颜色数。 - 接下来的 $n-1$ 行，每行包含两个整数“$x$ $y$”，表示有一条边连接节点 $x$ 和节点 $y$。节点编号从 $1$ 到 $n$。

对于每个测试用例，输出一行，格式为“Case #$X$: $Y$”，其中 $X$ 是测试用例编号（从 $1$ 开始），$Y$ 是该测试用例的答案。

**样例解释** 在第一个样例中，树有四个节点。每个节点都与其它三个节点中的一个相连。每对这些边都是相邻的，因此要实现彩虹染色，所有边必须染成不同的颜色。因此有 $10 \times 9 \times 8 = 720$ 种彩虹染色方案。 在第二个样例中，树本身是一条包含 $4$ 条边的路径，且有 $3$ 种颜色。前三条边必须染成不同的颜色，因此有 $3 \times 2 \times 1$ 种染色方式，第四条边只有一种选择，所以总共有 $6$ 种彩虹染色方案。 **数据范围** - $1 \leq k \leq 1000000000$ - 所有节点编号均在 $1$ 到 $n$ 之间。 **小数据范围（9 分，测试点 1 - 可见）** - $1 \leq C \leq 100$ - $2 \leq n \leq 20$ **大数据范围（15 分，测试点 2 - 隐藏）** - $1 \leq C \leq 40$ - $2 \leq n \leq 500$ 由 ChatGPT 4.1 翻译