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

לאוניברסיטת קיוטו יש עץ סמלי מפואר המשמש כעץ הסמל שלה.

K-kun, שהתרשם מהעץ הסמלי הזה, יצר העתק שלו כעץ מושרש עם $N$ צמתים.

צמתי העץ ממוספרים $1, 2, \dots, N$, שורש העץ הוא צומת $1$, והקשת ה-$i$ מחברת בין הצמתים $u_i$ ו-$v_i$.

מכיוון שחשב שהעתקה בלבד של העץ תהיה משעממת, K-kun רושם מספר שלם אי-שלילי על כל צומת של העץ כך שמתקיימים התנאים הבאים.

תנאים

  • המספר השלם הרשום על השורש הוא $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.