241 . 小風愛塗色

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

abcabcabc

User's AC Ratio

100.0% (2/2)

Submission's AC Ratio

100.0% (2/2)

Tags

ioicamp ioicamp-2020

Description

小風是一個愛塗色的人，他看到甚麼東西都想要塗色。今天他拿到了一棵 $N$ 個點的樹，其中 $1$ 號是這棵樹的根，而且他手上有 $K$ 種不同顏色的顏料，他想要把每個點都塗上這 $K$ 種顏色其中的一種，並且滿足以下條件：對於任意兩個節點 $x, y$，他們的最低公共祖先被塗上的顏色要和 $x, y$ 其中之一一樣。請幫小風算算看他有多少種不同的塗色方式吧！ 

Input Format

輸入第一行有兩個正整數 $N, K$，代表這棵樹有 $N$ 個點且小風有 $K$ 種不同的顏料。

接下來 $N - 1$ 行每一行有兩個正整數 $x, y$，代表樹上的一條邊。

  • $1 \leq K \leq N \leq 2 \times 10^ 5$
  • $1 \leq x, y \leq N$
  • 保證輸入的圖為一棵樹

Output Format

對於每一組輸入，請輸出一個整數代表有多少種不同的塗色方法滿足條件，請輸出答案$\bmod{10^ 9 + 7}$。

Sample Input 1

4 3
1 2
2 3
2 4

Sample Output 1

45

Sample Input 2

5 2
1 2
1 3
2 4
2 5

Sample Output 2

14

Hints

在一棵樹上，兩個點 $x, y$ 的最低公共祖先是兩個點分別到根節點的路徑上深度最大的共同節點。

Problem Source

IOICamp 2020 Day2 pC

Subtasks

No. Testdata Range Constraints Score
1 0~1 範例測資 0
2 0~54 無額外限制 100

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1000 262144 65536 1 2
1 1000 262144 65536 1 2
2 1000 262144 65536 2
3 1000 262144 65536 2
4 1000 262144 65536 2
5 1000 262144 65536 2
6 1000 262144 65536 2
7 1000 262144 65536 2
8 1000 262144 65536 2
9 1000 262144 65536 2
10 1000 262144 65536 2
11 1000 262144 65536 2
12 1000 262144 65536 2
13 1000 262144 65536 2
14 1000 262144 65536 2
15 1000 262144 65536 2
16 1000 262144 65536 2
17 1000 262144 65536 2
18 1000 262144 65536 2
19 1000 262144 65536 2
20 1000 262144 65536 2
21 1000 262144 65536 2
22 1000 262144 65536 2
23 1000 262144 65536 2
24 1000 262144 65536 2
25 1000 262144 65536 2
26 1000 262144 65536 2
27 1000 262144 65536 2
28 1000 262144 65536 2
29 1000 262144 65536 2
30 1000 262144 65536 2
31 1000 262144 65536 2
32 1000 262144 65536 2
33 1000 262144 65536 2
34 1000 262144 65536 2
35 1000 262144 65536 2
36 1000 262144 65536 2
37 1000 262144 65536 2
38 1000 262144 65536 2
39 1000 262144 65536 2
40 1000 262144 65536 2
41 1000 262144 65536 2
42 1000 262144 65536 2
43 1000 262144 65536 2
44 1000 262144 65536 2
45 1000 262144 65536 2
46 1000 262144 65536 2
47 1000 262144 65536 2
48 1000 262144 65536 2
49 1000 262144 65536 2
50 1000 262144 65536 2
51 1000 262144 65536 2
52 1000 262144 65536 2
53 1000 262144 65536 2
54 1000 262144 65536 2
Submit
Back to Top