← 返回题目列表

AtCoder · utpc2025_b

B. 二叉树计数

中文机器翻译题面 查看原题

配点 : 100 点

問題文

頂点 1, 2, \dots, N 的 可以考虑 N 计算满足以下所有条件的顶点组成的二叉树的数量。 对于 998244353 求余数。

  • 各 i = 1, 2, \dots, N ,顶点 i 的 可以考虑目的地是 i 。特别是,顶点 1 是根。
  • 各 i = 1, 2, \dots, M ,顶点 A_i 的 可以考虑传递订单是 B_i 。 关于

但是,2 当顶点不同时,两个二叉树是不同的。 v 存在且以下条件之一成立:

  • v 的左子节点或顶点编号是否存在不同。
  • v 的右子节点或顶点号是否存在不同。
什么是二叉树? 二叉树意味着每个顶点最多 1 剩下的孩子最多 它是一棵有根树,具有 1 右子节点。
什么是传球顺序和传球顺序? 二叉树的每个顶点 v 的到达和传递顺序如下面的伪代码所示。 执行 dfs(根) 时记录 preorder[v] 和 定义为 inorder[v] 的值。
pre_cnt = 1; in_cnt = 1
def dfs(v):
    preorder[v] = pre_cnt; pre_cnt += 1
    if v の左の子が存在する:
        dfs(v の左の子)
    inorder[v] = in_cnt; in_cnt += 1
    if v の右の子が存在する:
        dfs(v の右の子)

制約

  • 所有输入均为整数
  • 1 \leq M \leq N \leq 500
  • 1 \leq A_i, B_i \leq N
  • A_i \neq A_j \ (i \neq j)
  • B_i \neq B_j \ (i \neq j)

入力

输入是按以下格式从标准输入给出的。

N M
A_1 B_1
A_2 B_2
\vdots
A_M B_M

出力

答案 1 行输出。


入力例 1

3 1
2 1

出力例 1

2

下一步 2 两个二叉树满足条件。

  • 頂点 1 是根和顶点 2 是顶点 1 的左子节点,顶点 是 3 是顶点 2 右子树的二叉树。在这棵二叉树中,
    • 頂点 1 的目的地顺序是 1,传递顺序是 是 3 。
    • 頂点 2 的目的地顺序是 2,传递顺序是 是 1 。
    • 頂点 3 的目的地顺序是 3,传递顺序是 是 2 。
  • 頂点 1 是根和顶点 2 是顶点 1 的左子节点,顶点 是 3 是顶点 1 右子树的二叉树。在这棵二叉树中,
    • 頂点 1 的目的地顺序是 1,传递顺序是 是 2 。
    • 頂点 2 的目的地顺序是 2,传递顺序是 是 1 。
    • 頂点 3 的目的地顺序是 3,传递顺序是 是 3 。

入力例 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