TopCoder

Caido
主唱太拼命了

User's AC Ratio

100.0% (12/12)

Submission's AC Ratio

95.6% (43/45)

Tags

Description

鯞鷺國是一個特別的王國,王國一共有 $N$ 個景點,編號依序為 $1, 2, \ldots, N$。兩景點之間可能會有道路連接,使得任兩個景點之間恰好有一條不經過重複景點的路徑。簡單來說,鯞鷺國的景點呈現樹狀結構。

鯞鷺國住著 $K$ 個人,住在這裡的人非常喜歡走路。每天早上,第 $i$ 個人會決定兩個景點 $a_i, b_i$ 且 $a_i \neq b_i$,並從編號 $a_i$ 的景點走到編號 $b_i$ 的景點。他們很喜歡「一起走的路」,所以只要他們發現有至少一條道路是 $K$ 個人都有走過的(不管哪個方向都算走過),他們就會很開心。

現在給定鯞鷺國的 $N - 1$ 條道路,你能幫幫他們計算有幾種挑選景點的方法可以讓他們開心嗎?兩種方法不同若存在一個 $i$ 使所選擇的 $a_i$ 或 $b_i$ 有至少一個不同。因為方法數很多,請輸出答案除以 $998244353$ 的餘數。

Input Format

輸入第一行有兩個正整數 $N, K$,代表鯞鷺國的景點數量的以及居民的數量。

接下來 $N - 1$ 行,第 $i$ 行有兩個正整數 $u_i, v_i$,代表編號 $u_i$ 的景點與編號 $v_i$ 的景點之間有一條邊。

  • $2 \leq N \leq 2 \times 10^ 5$
  • $1 \leq K \leq 2 \times 10^ 5$
  • $1 \leq u_i, v_i \leq N$
  • 保證輸入為一棵樹

Output Format

請輸出一行,該行有一個整數,代表方法數除以 $998244353$ 的餘數。

Sample Input 1

5 3
4 2
4 1
3 4
5 2

Sample Output 1

2912

Sample Input 2

10 10
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10

Sample Output 2

585448389

Sample Input 3

15 56562
2 12
9 1
12 11
14 4
13 6
7 12
10 14
5 4
12 13
7 3
8 12
15 4
7 1
12 14

Sample Output 3

272288838

Hints

Problem Source

Subtasks

No. Testdata Range Constraints Score
1 0~2 範例測資 0
2 0~22 $N \leq 2000$ 40
3 0~47 無額外限制 60

Testdata and Limits

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