Description：

给一棵树，对它做点分治，不一定按重心划分，求有多少种不同的点分树。

$1\leqslant n\leqslant 2000$

Solution：

首先考虑如果把一棵树的某一条边断掉，他两边的点分树的形态是什么样的，发现一定是某一些点的父亲原来在另一个集合，现在只能找到最靠下的一个在这边集合的祖先作为他的新的祖先，然后我们在考虑如何把两个点分树合并起来，发现如果有一个点他的父亲在另外一个集合，那么这个父亲一定在这条边这个集合那一侧的端点到点分树的根的路径上，因为这个父亲的子树既有另一个集合的，又有这个集合的，显然必须过这条边，显然对于另一个集合也是一样的，那么这实际上就相当于把这条边的两个端点的所有祖先按任意顺序拼在一起，因此设状态 $f[i][j]$ 表示以 $i$ 为根的子树构成的点分树中 $i$ 的深度是 $j$ 的方案数，列出朴素的 $DP$ 方程就是： $$ f[k][i]=\sum_{j=1}^if[k][j]\times\sum_{l=i-j}^nf[e[i].to][l]\binom{i-1}{j-1} $$ 显然后面那个组合数和 $l$ 没有关系因此可以后缀和优化。

Code：

没有代码