Universal Cup Judging System

Universal Cup

Limite de temps : 2.0 s Limite de mémoire : 1024 MB Points totaux : 100 Hackable ✓
Statistiques

Kyoto-universitetet har et storslått symbolsk tre som sitt symboltre.

Imponert over dette symbolske treet lagde K-kun en kopi av det som et rotfestet tre med $N$ noder.

Nodene i treet er nummerert $1, 2, \dots, N$, roten i treet er node $1$, og den $i$-te kanten forbinder nodene $u_i$ og $v_i$.

Siden K-kun syntes det ville være uinteressant bare å kopiere treet, skriver han et ikke-negativt heltall på hver node i treet slik at følgende betingelser er oppfylt.

Betingelser

  • Heltallet som står på roten er $K$.
  • For hver node bortsett fra roten er heltallet som står på denne noden høyst lik heltallet som står på forelderen dens.

Finn resten når antallet mulige måter å skrive heltall på nodene i treet på divideres med $998244353$.

To måter å skrive heltall på nodene på regnes som forskjellige hvis og bare hvis det finnes en node der heltallet som står på noden er forskjellig.

Inndata

Den første linjen inneholder heltallene $N, K$ adskilt med mellomrom. ($2 \le N \le 3000, 1 \le K \le 10^9$)

Hver av de påfølgende $N - 1$ linjene inneholder heltallene $u_i, v_i$ adskilt med mellomrom, som representerer en kant i treet.

Utdata

Skriv ut svaret modulo $998244353$.

Eksempler

Eksempelinndata 1

5 1
1 2
1 3
3 4
3 5

Eksempelutdata 1

10

Eksempelinndata 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

Eksempelutdata 2

623173536

Forklaring

For det første eksempelet oppfyller følgende $10$ tilordninger av heltall til nodene $1, 2, 3, 4, 5$ betingelsene.

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