Universal Cup Judging System

Universal Cup

Límite de tiempo: 2.0 s Límite de memoria: 1024 MB Puntuación total: 100 Hackeable ✓
Estadísticas

京都大學有一棵宏偉嘅標誌樹作為佢嘅象徵。

K 君對呢棵標誌樹印象好深,於是將佢複製成一棵有 $N$ 個頂點嘅有根樹。

樹嘅頂點編號為 $1, 2, \dots, N$,樹根係頂點 $1$,第 $i$ 條邊連接頂點 $u_i$ 同 $v_i$。

K 君覺得齋係複製棵樹太悶,於是喺樹嘅每個頂點上面寫一個非負整數,令到滿足以下條件。

條件

  • 根節點上面寫嘅整數係 $K$。
  • 對於除咗根節點之外嘅每個頂點,嗰個頂點上面寫嘅整數唔超過佢父節點上面寫嘅整數。

求喺樹嘅頂點上面寫整數嘅可能方案數除以 $998244353$ 嘅餘數。

當且僅當存在某個頂點,令到寫喺嗰個頂點上面嘅整數唔同嗰陣,兩種寫整數嘅方案先至視為唔同。

輸入格式

第一行包含用空格隔開嘅整數 $N, K$。($2 \le N \le 3000, 1 \le K \le 10^9$)

接下來嘅 $N - 1$ 行,每行包含用空格隔開嘅整數 $u_i, v_i$,代表樹嘅一條邊。

輸出格式

輸出答案對 $998244353$ 取模之後嘅結果。

範例

範例輸入 1

5 1
1 2
1 3
3 4
3 5

範例輸出 1

10

範例輸入 2

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

範例輸出 2

623173536

說明

對於第一個範例,以下 $10$ 種對頂點 $1, 2, 3, 4, 5$ 嘅整數分配方案滿足條件。

  • $1, 0, 0, 0, 0$
  • $1, 0, 1, 0, 0$
  • $1, 0, 1, 0, 1$
  • $1, 0, 1, 1, 0$
  • $1, 0, 1, 1, 1$
  • $1, 1, 0, 0, 0$
  • $1, 1, 1, 0, 0$
  • $1, 1, 1, 0, 1$
  • $1, 1, 1, 1, 0$
  • $1, 1, 1, 1, 1$

Editorials

IDTypeStatusTitlePosted ByLast UpdatedActions
#1528EditorialOpen题解jianglyView

Discussions

About Discussions

The discussion section is only for posting: General Discussions (problem-solving strategies, alternative approaches), and Off-topic conversations.

This is NOT for reporting issues! If you want to report bugs or errors, please use the Issues section below.

Open Discussions 0
No discussions in this category.

Issues

About Issues

If you find any issues with the problem (statement, scoring, time/memory limits, test cases, etc.), you may submit an issue here. A problem moderator will review your issue.

Guidelines:

  1. This is not a place to publish discussions, editorials, or requests to debug your code. Issues are only visible to you and problem moderators.
  2. Do not submit duplicated issues.
  3. Issues must be filed in English or Chinese only.
Active Issues 0
No issues in this category.
Closed/Resolved Issues 0
No issues in this category.