Universal Cup Judging System

Universal Cup

时间限制: 2.0 s 内存限制: 1024 MB 总分: 100 可 Hack ✓
统计

Universitas Kyoto memiliki pohon simbolis yang megah sebagai pohon lambangnya.

Terpesona oleh pohon simbolis ini, K-kun membuat salinannya sebagai pohon berakar dengan $N$ simpul.

Simpul-simpul pohon diberi label $1, 2, \dots, N$, akar pohon adalah simpul $1$, dan sisi ke-$i$ menghubungkan simpul $u_i$ dan $v_i$.

Karena merasa bahwa sekadar menyalin pohon tersebut kurang menarik, K-kun menuliskan sebuah bilangan bulat tak negatif pada setiap simpul pohon sehingga syarat-syarat berikut terpenuhi.

Syarat-syarat

  • Bilangan bulat yang tertulis pada akar adalah $K$.
  • Untuk setiap simpul selain akar, bilangan bulat yang tertulis pada simpul tersebut paling banyak sebesar bilangan bulat yang tertulis pada induknya.

Carilah sisa pembagian banyaknya cara yang mungkin untuk menuliskan bilangan bulat pada simpul-simpul pohon dengan $998244353$.

Dua cara penulisan bilangan bulat pada simpul-simpul dianggap berbeda jika dan hanya jika terdapat suatu simpul yang memiliki bilangan bulat tertulis yang berbeda.

Masukan

Baris pertama berisi bilangan bulat $N, K$ yang dipisahkan oleh spasi. ($2 \le N \le 3000, 1 \le K \le 10^9$)

Masing-masing dari $N - 1$ baris berikutnya berisi bilangan bulat $u_i, v_i$ yang dipisahkan oleh spasi, yang menyatakan sebuah sisi dari pohon.

Keluaran

Keluarkan jawaban modulo $998244353$.

Contoh

Contoh Masukan 1

5 1
1 2
1 3
3 4
3 5

Contoh Keluaran 1

10

Contoh Masukan 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

Contoh Keluaran 2

623173536

Catatan

Untuk contoh pertama, $10$ pemberian nilai bilangan bulat berikut pada simpul $1, 2, 3, 4, 5$ memenuhi syarat.

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