分数: 500 点
问题陈述
你有一棵树 N 顶点和 N-1 边缘。顶点已编号 1 to N,以及 i第一条边连接顶点 a_i 和 b_i.
您有以下着色材料 K 颜色。 对于树中的每个顶点,您将选择以下之一 K 颜色来绘制它,以满足以下条件:
- 如果两个不同顶点之间的距离 x 和 y 小于或等于二, x 和 y 有不同的颜色。
画树有多少种方法?求计数模数 1\ 000\ 000\ 007.
什么是树?
树是一种图。详细请参见: 维基百科“树(图论)”
什么是距离?
两个顶点之间的距离 x 和 y 是必须遍历才能获得的最小边数 x to y.
约束
- 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.
示例输入 1
4 3 1 2 2 3 3 4
示例输出 1
6

有六种方法来绘制树。
示例输入 2
5 4 1 2 1 3 1 4 4 5
示例输出 2
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
示例输出 3
271414432