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.