AT_abc133_e [ABC133E] Virus Tree 2

题目描述

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

你有 $K$ 种颜色的颜料。你需要给树的每个顶点选择一种颜色进行涂色，要求满足以下条件：

• 对于任意两个距离不超过 $2$ 的不同顶点 $x,y$，顶点 $x$ 和顶点 $y$ 的颜色必须不同。

请计算有多少种不同的涂色方法。将结果对 $1,000,000,007$ 取模后输出。

关于树

树是一种特殊的图。详情请参考：Wikipedia「木 (数学)」。

关于距离

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

输入格式

输入通过标准输入按以下格式给出：

$N$ $K$
$a_1$ $b_1$
$a_2$ $b_2$
$\cdots$
$a_{N-1}$ $b_{N-1}$

输出格式

输出树的所有合法涂色方法数，对 $1,000,000,007$ 取模后的结果。

样例 1

输入

4 3
1 2
2 3
3 4

输出

6

样例 2

输入

5 4
1 2
1 3
1 4
4 5

输出

48

样例 3

输入

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$
• 输入保证给定的图是一棵树。

样例解释 1

共有 $6$ 种不同的涂色方法。

由 ChatGPT 4.1 翻译