题目描述

译自 CCO 2025 Day1 T2「Tree Decorations」。

Mateo 最近为他的圣诞树找到了完美的装饰——更多的树！

具体来说，他的圣诞树是一棵有根树 $T$，初始有 $M$ 个节点，全部被涂成绿色。他还有另一棵有根树 $D$，用作装饰的参考。Mateo 按照以下过程来放置他的装饰：

• 对于 $D$ 中的每个节点 $i$，他会复制以 $i$ 为根的子树，记这份复制为 $C_i$。然后，他将 $C_i$ 中的节点涂成红色。最后，他选择 $T$ 中的某个绿色节点作为 $C_i$ 根节点的父节点，并通过一条边将它们连接起来。

在完成所有装饰后，$T$ 最终包含 $N$ 个节点。不幸的是，他发现自己忘了记录 $D$ 的具体结构！更糟的是，他不小心把水洒在了 $T$ 上，洗掉了所有节点的颜色。此后，他将 $T$ 的根节点标记为 $1$，并将其他节点从 $2$ 到 $N$ 依次编号。

目前他唯一的信息是 $T$ 的最终状态以及 $M$ 的值。请帮助他计算出最初可能使用的 $D$ 的数量，其中如果两个 $D$ 在结构上不同，则认为它们是不同的可能性。

有根树 $A$ 和 $B$ 被认为在结构上相同，当且仅当它们有相同数量的节点 $S$，并且存在一种方式将 $A$ 的节点从 $1$ 到 $S$ 编号，同样将 $B$ 的节点从 $1$ 到 $S$ 编号，使得：

• 它们的根节点编号相同。
• 在 $A$ 中编号为 $x$ 和 $y$ 的节点之间有边，当且仅当在 $B$ 中编号为 $x$ 和 $y$ 的节点之间也有边。

否则，$A$ 和 $B$ 被认为在结构上不同。

输入格式

第一行包含两个用空格分隔的整数 $N$ 和 $M$。

接下来的 $N-1$ 行，每行包含两个用空格分隔的整数 $u_i$ 和 $v_i$ $(1 \leq u_i, v_i \leq N, u_i \neq v_i)$，描述 $T$ 中连接节点 $u_i$ 和 $v_i$ 的一条边。注意 $T$ 的根节点为 $1$。

输出格式

输出一个整数，表示 Mateo 最初可能使用的 $D$ 的数量，其中如果两个 $D$ 在结构上不同，则认为它们是不同的可能性。

8 3
1 2
1 3
1 4
2 5
2 6
3 7
3 8

1

可以证明，唯一可能的 $D$ 是：

可以通过以下方式得到 $T$：

在上图中，红色部分是作为装饰添加的部分，而绿色填充部分表示 $T$ 的初始状态。虚线表示连接装饰和树的边。

14 5
1 2
1 3
3 4
3 5
1 6
6 7
7 8
7 9
2 10
10 11
10 12
10 13
10 14

2

$D$ 的第一种可能性是：

使用这种可能性，可以通过以下方式得到 $T$：

$D$ 的第二种可能性是：

使用这种可能性，可以通过以下方式得到 $T$：

数据范围与提示

详细子任务附加限制及分值如下表所示。