#P18002. Binary Tree Counting
Binary Tree Counting
Binary Tree Counting
求有多少棵含 个顶点、顶点编号为 的二叉树,满足:
- 对每个 ,顶点 的先序遍历序号恰好为 ,因此根为顶点 。
- 对每个 ,顶点 的中序遍历序号为 。
答案对 取模。
这里二叉树是每个顶点至多有一个左儿子和一个右儿子的有根树。只要存在某个顶点,其左儿子或右儿子的存在性或编号不同,两棵树就视为不同。仅有一个儿子时,左儿子和右儿子的情况也不同。
先序、中序遍历序号由以下过程定义,两个计数器初值均为 :
dfs(v):
preorder[v] = pre_cnt; pre_cnt += 1
如果 v 有左儿子:dfs(v 的左儿子)
inorder[v] = in_cnt; in_cnt += 1
如果 v 有右儿子:dfs(v 的右儿子)
对根调用 dfs。
输入格式
第一行两个整数 。接下来 行,每行两个整数 。
输出格式
输出满足条件的二叉树数量对 取模的结果。
数据范围
,。所有 两两不同,所有 两两不同。
样例 1
输入
3 1
2 1
输出
2
样例 2
输入
5 3
1 3
2 5
4 2
输出
0
样例 3
输入
30 6
12 26
9 5
15 14
19 15
4 2
10 4
输出
550222816