冰堂美智留

首先考虑一下这个 $k=1$ 的时候 搜索树会长成什么样子，容易发现大概就是，与一个点串在一起的所有边都会变成一条链。

容易发现确定了起点的边之后，对于每一条链的起点是全部确定了的，而链剩下的点的搜索顺序就随便了，所以 $k=1$ 的时候有一个优秀的做法，那就是直接把所有点的度数减一的阶乘乘起来。

然后 $k=2$ 就不能够这么做，为啥呢，因为有一种情况可能是两个关键边都能够到达的，以起点来刻画这个搜索树非常的不牛，我们考虑换一个更牛的刻画。

有的人想到，既然我们能够构造小链，那我们为什么不直接通过记录每个连痛块里面有没有关键边来计数对于每个节点能够构造出来的本质不同的链的数量呢，实际上是不行的，因为起点是限定的连续的，直接乘起来肯定不行。

起点刻画不行是因为会重复，会重复那就是因为有的链既能正着跑也能反着跑，然后你发现我们不能做的根源就是因为这条链的形态，那我们考虑把链拉下来计数。

容易发现，每个点的链是可以首尾相接在一起直到最后到度数为 $1$ 的点上，形成一条大链，这条链是否能够达成，那就相当于是询问这条链中间有没有关键边，如果有的话，对于这条大链的计数是容易的（具体地，链上节点贡献度数减二的阶乘，其余节点贡献度数减一的阶乘），而这就是本质不同的生成树个数，原因很显然，如果要重复那么必然在这条包含起点的链上重复（也就是开头和结尾搜出了重复的节点），那么我们直接对这条链计数就解决掉了这个问题。

然后具体实现就比较简单，考虑直接合并子节点状态就可以了。