该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

Virus Tree 2

题目描述

你被给定了一棵有 $N$ 个顶点和 $N-1$ 条边的树。顶点编号为 $1$ 到 $N$，第 $i$ 条边连接顶点 $a_i$ 和 $b_i$。 你有 $K$ 种颜色的着色材料。 对于树中的每个顶点，你将从 $K$ 种颜色中选择一种来给它着色，使得满足以下条件：

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

有多少种为树着色的方法？求其对 $1\ 000\ 000\ 007$ 取模的值。

输入格式

标准输入的给出格式如下： $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

提示

$1 \leq N,K \leq 10^5$ $1 \leq a_i,b_i \leq N$ 给定的图是树。 共有六种为树着色的方法。

标签: AtCoder|abc133E

来源

AtCoder|abc133E