Logo Universal Online Judge

UOJ

时间限制:1 s 空间限制:512 MB

#2781. 二叉树比大小

Statistics

题目描述

用 $0$ 代表空树,如果一个节点没有左子树,那么认为它的左子树是空树(右子树同理)。对任意二叉树 $A$,$0\le A$ 成立; 对任意非空二叉树 $A$,$A\le0$ 不成立。用 $\text{ls}$ 代表左子树,$\text{rs}$ 代表右子树,则对于非空二叉树 $A,B$,$A\le B$ 当且仅当 $\text{ls}(A)\le\text{ls}(B)$ 且 $\text{rs}(B)\le\text{rs}(A)$。$A=B$ 当且仅当 $A\le B$ 且 $B\le A$。否则 $A\not=B$。

给定节点编号为 $1$ ~ $n$ 的二叉树 $A$。$B$ 的初始值为 $A$。对 $B$ 重复进行以下操作:任选 $B$ 的一个儿子数量不超过 $1$ 的节点,为这个节点增加一个儿子(使得 $B$ 仍然是二叉树)。左右有区别。

问共有多少不同(定义见上文)的 $B$ 满足 $B$ 的节点数为 $n+m$ 且 $A\le B$。

输入格式

第一行是两个整数 $n,m$。

接下来 $n$ 行,给出二叉树 $A$。第 $i+1$ 行有两个整数,第一个是 $i$ 号节点的左儿子编号,第二个是右儿子编号(如果没有左儿子/右儿子,用 $0$ 代替)。

输出格式

一个整数,表示满足条件的 $B$ 的数量,对 $1914270647$(一个质数)取模。

样例一

input

4 2
2 0
3 0
0 4
0 0

output

5

explanation

样例二

input

6 3
0 0
0 3
6 4
0 1
2 0
0 0

output

48

样例三

input

1 1427
0 0

output

1224214018

数据范围

所有数据满足 $1\le n,m\le10^6$。