Universal Cup Judging System

Universal Cup

Time Limit: 2.0 s Memory Limit: 1024 MB Total points: 100 Hackable ✓
Statistics

Төмендегі шарттардың барлығын қанағаттандыратын, $1, 2, \dots, N$ деп белгіленген $N$ төбесі бар екілік ағаштардың (екілік ағаш — әрбір төбесінің ең көбі бір сол жақ ұрпағы және ең көбі бір оң жақ ұрпағы болатын түбірлі ағаш) санын табыңыз және нәтижені $998244353$ модулі бойынша шығарыңыз.

  • Әрбір $i = 1, 2, \dots, N$ үшін $i$ төбесінің тура аралау индексі (preorder index) $i$-ге тең. Атап айтқанда, $1$ төбесі — түбір.
  • Әрбір $i = 1, 2, \dots, M$ үшін $A_i$ төбесінің ішкі аралау индексі (inorder index) $B_i$-ге тең.

Егер келесі шарттардың кемінде біреуі орындалатындай $v$ төбесі табылса, екі екілік ағаш әртүрлі деп есептеледі:

  • $v$ төбесінің сол жақ ұрпағының бар-жоғы немесе төбе нөмірі өзгеше.
  • $v$ төбесінің оң жақ ұрпағының бар-жоғы немесе төбе нөмірі өзгеше.

Екілік ағаштағы әрбір $v$ төбесінің тура аралау индексі мен ішкі аралау индексі төмендегі псевдокодта dfs(root) орындалған кезде сәйкесінше preorder[v] және inorder[v] массивтеріне жазылатын мәндер ретінде анықталады:

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.