Universal Cup Judging System

Universal Cup

시간 제한: 2.0 s 메모리 제한: 1024 MB 총점: 100 해킹 가능 ✓
통계

מצא את מספר העצים הבינאריים (עץ בינארי הוא עץ מושרש שבו לכל צומת יש לכל היותר בן שמאלי אחד ולכל היותר בן ימני אחד) עם $N$ צמתים הממוספרים $1, 2, \dots, N$ המקיימים את כל התנאים הבאים, והדפס את התוצאה מודולו $998244353$.

  • עבור כל $i = 1, 2, \dots, N$, אינדקס הסריקה התחילי (preorder index) של צומת $i$ הוא $i$. בפרט, צומת $1$ הוא השורש.
  • עבור כל $i = 1, 2, \dots, M$, אינדקס הסריקה התוכי (inorder index) של צומת $A_i$ הוא $B_i$.

שני עצים בינאריים נחשבים שונים אם קיים צומת $v$ כך שלפחות אחד מהתנאים הבאים מתקיים:

  • הקיום או מספר הצומת של הבן השמאלי של $v$ שונה.
  • הקיום או מספר הצומת של הבן הימני של $v$ שונה.

אינדקס הסריקה התחילי ואינדקס הסריקה התוכי של כל צומת $v$ בעץ בינארי מוגדרים בתור הערכים הנרשמים ב-preorder[v] וב-inorder[v], בהתאמה, בעת הרצת dfs(root) בפסאודו-קוד הבא:

pre_cnt = 1; in_cnt = 1
def dfs(v):
    preorder[v] = pre_cnt; pre_cnt += 1
    if v has a left child:
        dfs(left child of v)
    inorder[v] = in_cnt; in_cnt += 1
    if v has a right child:
        dfs(right child of v)

קלט

הקלט ניתן בפורמט הבא:

$$\begin{aligned} &N \ M \\ &A_1 \ B_1 \\ &A_2 \ B_2 \\ &\vdots \\ &A_M \ B_M \end{aligned}$$

  • כל ערכי הקלט הם מספרים שלמים.
  • $1 \le M \le N \le 500$
  • $1 \le A_i, B_i \le N$
  • $A_i \ne A_j$ ($i \ne j$)
  • $B_i \ne B_j$ ($i \ne j$)

פלט

הדפס את התשובה בשורה בודדת.

דוגמאות

קלט 1

3 1
2 1

פלט 1

2

קלט 2

5 3
1 3
2 5
4 2

פלט 2

0

קלט 3

30 6
12 26
9 5
15 14
19 15
4 2
10 4

פלט 3

550222816

הערה

בדוגמה הראשונה, ישנם בדיוק שני עצים בינאריים המקיימים את התנאים. באחד מהם צומת $1$ הוא השורש, צומת $2$ הוא הבן השמאלי של צומת $1$, וצומת $3$ הוא הבן הימני של צומת $2$. בשני צומת $1$ הוא השורש, צומת $2$ הוא הבן השמאלי של צומת $1$, וצומת $3$ הוא הבן הימני של צומת $1$. אינדקסי הסריקה התחיליים והתוכיים שלהם עקביים עם האילוצים הנתונים.

בדוגמה השנייה, אף עץ בינארי אינו מקיים את התנאים.

Editorials

IDTypeStatusTitlePosted ByLast UpdatedActions
#1406EditorialOpen题解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.