TopCoder

Caido
主唱太拼命了

User's AC Ratio

100.0% (12/12)

Submission's AC Ratio

95.6% (43/45)

Tags

Description

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

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

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

Input Format

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

接下來 N1 行,第 i 行有兩個正整數 ui,vi,代表編號 ui 的景點與編號 vi 的景點之間有一條邊。

  • 2N2×105
  • 1K2×105
  • 1ui,viN
  • 保證輸入為一棵樹

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

IOICamp 2024 Day6 pE

Subtasks

No. Testdata Range Constraints Score
1 0~2 範例測資 0
2 0~22 N2000 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