病毒树 2

题目描述

给定一棵有 $N$ 个顶点、$N-1$ 条边的树。顶点标有编号 $1,2,...,N$,第 $i$ 条边连接顶点 $a_i, b_i$。

你有 $K$ 种颜色的颜料。你打算给树的每个顶点从 $K$ 种颜色中选 1 种涂色,使得满足以下条件:

• 若两个不同顶点 $x,y$ 之间的距离不超过 $2$,则顶点 $x$ 的颜色与顶点 $y$ 的颜色不同。

有多少种给树涂色的方法?请输出总数除以 $1,000,000,007$ 的余数。

关于树:

树是图的一种。

关于距离:

两个顶点 $x,y$ 之间的距离,是指从 $x$ 到达 $y$ 所需要经过的最少边数。

输入格式

输入按以下格式从标准输入给出:

$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

涂色方法共有 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

数据范围

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