← 返回题目列表

AtCoder · abc133_e

E. 病毒树2

中文机器翻译题面 查看原题

分数: 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

Figure

有六种方法来绘制树。


示例输入 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