Universal Cup Judging System

Universal Cup

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

Finndu fjölda tvíundartrjáa (tvíundartré er rótað tré þar sem hver hnútur hefur í mesta lagi eitt vinstra barn og í mesta lagi eitt hægra barn) með $N$ hnútum merktum $1, 2, \dots, N$ sem uppfylla öll eftirfarandi skilyrði, og prentaðu niðurstöðuna modulo $998244353$.

  • Fyrir hvert $i = 1, 2, \dots, N$ er forraðarvísir (preorder index) hnúts $i$ jafn $i$. Sér í lagi er hnútur $1$ rótin.
  • Fyrir hvert $i = 1, 2, \dots, M$ er innraðarvísir (inorder index) hnúts $A_i$ jafn $B_i$.

Tvö tvíundartré teljast ólík ef til er hnútur $v$ þannig að að minnsta kosti annað af eftirfarandi gildir:

  • Tilvist eða hnútanúmer vinstra barns $v$ er ólíkt.
  • Tilvist eða hnútanúmer hægra barns $v$ er ólíkt.

Forraðarvísir og innraðarvísir hvers hnúts $v$ í tvíundartré eru skilgreindir sem gildin sem skráð eru í preorder[v] og inorder[v], í sömu röð, þegar dfs(root) er keyrt í eftirfarandi sauðakóða:

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)

Inntak

Inntakið er gefið á eftirfarandi sniði:

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

  • Öll inntaksgildi eru heiltölur.
  • $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$)

Úttak

Prentaðu svarið á einni línu.

Dæmi

Inntak 1

3 1
2 1

Úttak 1

2

Inntak 2

5 3
1 3
2 5
4 2

Úttak 2

0

Inntak 3

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

Úttak 3

550222816

Athugasemd

Í fyrsta dæminu eru nákvæmlega tvö tvíundartré sem uppfylla skilyrðin. Annað hefur hnút $1$ sem rót, hnút $2$ sem vinstra barn hnúts $1$ og hnút $3$ sem hægra barn hnúts $2$. Hitt hefur hnút $1$ sem rót, hnút $2$ sem vinstra barn hnúts $1$ og hnút $3$ sem hægra barn hnúts $1$. Forraðar- og innraðarvísar þeirra eru í samræmi við gefnar skorður.

Í öðru dæminu uppfyllir ekkert tvíundartré skilyrðin.

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.