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