Description

在图论中，树是一个连通、无向、无环的简单图。一个有 $n$ 个节点的树总是有 $n - 1$ 条边。

树中的一条路径是由一系列互不相同且相连的边组成的（路径中每对相邻的边共享一个顶点）。

考虑一棵有 $n$ 个顶点和 $n - 1$ 条边的树。你可以用 $k$ 种颜色中的任意一种来给每条边染色。

如果对边的染色满足：在树中任意长度为 $2$ 或 $3$ 的路径上，所有边的颜色都不同（即任意两条相邻的边颜色不同，任意三条连续的边颜色也都不同），则称这种染色为“彩虹染色”。

给定一棵树和颜色数 $k$，请你计算有多少种不同的彩虹染色方案。答案对 $1000000009$ 取模。

Input Format

输入的第一行是测试用例的数量 $C$。对于每个测试用例，包含如下内容：

• 第一行包含两个整数，格式为“$n$ $k$”。$n$ 表示树的节点数，$k$ 表示可用的颜色数。
• 接下来的 $n-1$ 行，每行包含两个整数“$x$ $y$”，表示有一条边连接节点 $x$ 和节点 $y$。节点编号从 $1$ 到 $n$。

Output Format

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

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

Case #1: 720
Case #2: 6

Hint

样例解释

在第一个样例中，树有四个节点。每个节点都与其它三个节点中的一个相连。每对这些边都是相邻的，因此要实现彩虹染色，所有边必须染成不同的颜色。因此有 $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 翻译