题意
分析
- 钦定 (k) 个点作为深度为奇数的点，有 (inom{n-1}{k-1}) 种方案。
- 将树黑白染色，这张完全二分图的生成树的个数就是我们钦定 (k) 个点之后合法的方案数。
- 然后就和 BZOJ4766文艺计算姬 一致了，假设两边点集大小分别为 (n,m) ，生成树个数就是 (n^{m-1}m^{n-1})
- 证明可以考虑 prufer 序列还原树时的操作，将所有点先放入 set 中，每次将没有出现在序列中的编号最小的点拿出来和 prufer 序列开头的点连边，并将这两个元素对应删除直到 set 的大小为2。对于选择的点集相同，出现顺序不同的两个方案，一定会保证每个集合的点所占据的位置是一个固定的集合，证明如下：
假设我们得到了两个点集相同的 prufer 序列：
(S_1 S_2 T_1 T_2 S_3)
(S_1 S_2 S_3 T_2 T_1)上述例子中的第三个位置，我们的 set 在前 3 个位置取出的点时相同的，(T_1,S_3) 不属于同一个点集，不可能都可以和 set 取出的第三个元素连边。
- 所以答案就是 (k^{n-k-1}(n-k)^{k-1}inom{n-1}{k-1})