Universal Cup Judging System

Universal Cup

Süre Sınırı: 2.0 s Bellek Sınırı: 1024 MB Toplam puan: 100 Hack'lenebilir ✓
İstatistikler

Kyotouniversitetet har ett magnifikt symboliskt träd som sitt vårdträd.

Imponerad av detta symboliska träd gjorde K-kun en kopia av det som ett rotat träd med $N$ hörn.

Trädets hörn är numrerade $1, 2, \dots, N$, trädets rot är hörn $1$, och den $i$-te kanten förbinder hörnen $u_i$ och $v_i$.

Eftersom K-kun tyckte att det vore ointressant att bara kopiera trädet skriver han ett icke-negativt heltal på varje hörn i trädet så att följande villkor är uppfyllda.

Villkor

  • Heltalet som skrivs på roten är $K$.
  • För varje hörn utom roten är heltalet som skrivs på det hörnet högst lika stort som heltalet som skrivs på dess förälder.

Beräkna resten när antalet möjliga sätt att skriva heltal på trädets hörn divideras med $998244353$.

Två sätt att skriva heltal på hörnen betraktas som olika om och endast om det finns något hörn där det skrivna heltalet skiljer sig åt.

Indata

Den första raden innehåller heltalen $N, K$ åtskilda av blanksteg. ($2 \le N \le 3000, 1 \le K \le 10^9$)

Var och en av de följande $N - 1$ raderna innehåller heltalen $u_i, v_i$ åtskilda av blanksteg, vilket representerar en kant i trädet.

Utdata

Skriv ut svaret modulo $998244353$.

Exempel

Exempelindata 1

5 1
1 2
1 3
3 4
3 5

Exempelutdata 1

10

Exempelindata 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

Exempelutdata 2

623173536

Förklaring

För det första exemplet uppfyller följande $10$ tilldelningar av heltal till hörnen $1, 2, 3, 4, 5$ villkoren.

  • $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.