病毒树2

分数：$500$ 分

问题描述

给定一个有 $N$ 个顶点和 $N-1$ 条边的树。顶点从 $1$ 到 $N$ 编号，第 $i$ 条边连接顶点 $a_i$ 和 $b_i$。

你有 $K$ 种颜色的染色材料。 对于树中的每个顶点，你要选择 $K$ 种颜色之一来染色，使得满足以下条件：

• 如果两个不同的顶点 $x$ 和 $y$ 的距离小于等于 $2$，则 $x$ 和 $y$ 的颜色不同。

有多少种方法可以给树染色？找到结果对 $1\ 000\ 000\ 007$ 取模的结果。

约束

• $1 \leq N,K \leq 10^5$
• $1 \leq a_i,b_i \leq N$
• 给定的图是一棵树。

输入

从标准输入读入的输入数据如下格式:

$N$ $K$

$a_1$ $b_1$

$a_2$ $b_2$

$.$

$.$

$.$

$a_{N-1}$ $b_{N-1}$

输出

打印给树染色的方法数量，结果对 $1\ 000\ 000\ 007$ 取模。

4 3
1 2
2 3
3 4

6

共有六种给树染色的方法。

5 4
1 2
1 3
1 4
4 5

48

16 22
12 1
3 1
4 16
7 12
6 2
2 15
5 16
14 16
10 11
3 10
3 13
8 6
16 8
9 12
4 3

271414432