E - Virus Tree 2 Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 500 点

問題文

N 頂点、N-1 辺を持つ木が与えられます。 頂点には番号 1,2,...,N がつけられており、i 番目の辺は頂点 a_i,b_i をつないでいます。

あなたは K 色の絵の具を持っています。 木の頂点それぞれに対して、以下の条件を満たすように、K 色の中から 1 色を選んで塗ることにしました。

  • 二つの異なる頂点 x,y 間の距離が 2 以下ならば、頂点 x の色と頂点 y の色は異なる。

木を塗り分ける方法は何通りあるでしょうか。 総数を 1,000,000,007 で割った余りを求めてください。

木とは

木とはグラフの一種です。詳しくはこちらをご覧ください: Wikipedia「木 (数学)」

距離とは

二つの頂点 x,y 間の距離とは、x から y に到達する際にたどる必要のある最小の辺数です。

制約

  • 1 \leqq N,K \leqq 10^5
  • 1 \leqq a_i,b_i \leqq 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

zu

塗り分け方は 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

Score : 500 points

Problem Statement

You are given a tree with N vertices and N-1 edges. The vertices are numbered 1 to N, and the i-th edge connects Vertex a_i and b_i.

You have coloring materials of K colors. For each vertex in the tree, you will choose one of the K colors to paint it, so that the following condition is satisfied:

  • If the distance between two different vertices x and y is less than or equal to two, x and y have different colors.

How many ways are there to paint the tree? Find the count modulo 1\ 000\ 000\ 007.

What is tree? A tree is a kind of graph. For detail, please see: Wikipedia "Tree (graph theory)"

What is distance? The distance between two vertices x and y is the minimum number of edges one has to traverse to get from x to y.

Constraints

  • 1 \leq N,K \leq 10^5
  • 1 \leq a_i,b_i \leq N
  • The given graph is a tree.

Input

Input is given from Standard Input in the following format:

N K
a_1 b_1
a_2 b_2
.
.
.
a_{N-1} b_{N-1}

Output

Print the number of ways to paint the tree, modulo 1\ 000\ 000\ 007.

Sample Input 1

4 3
1 2
2 3
3 4

Sample Output 1

6

Figure

There are six ways to paint the tree.

Sample Input 2

5 4
1 2
1 3
1 4
4 5

Sample Output 2

48

Sample Input 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

Sample Output 3

271414432