CF848D口胡

考虑如果边 /((u,w),(w,v)/) 是从 /((u,v)/) 分裂出来的，那么 /((u,v)/) 这条边有一个儿子，儿子是一个二元组为 /(((u,w),(w,v))/)。

容易发现所有本质不同的分裂方案对应所有本质不同的树。

考虑最小割对应什么。对于一个根节点，必须将所有儿子都割完之后才能割掉自己，所以有一个类似：

/[f[n][m]=/sum_{/sum(a_i+b_i+1)=n,/sum(/max(x_i,y_i))=m}f[a_i][x_i]/times f[b_i][y_i]
/]

的东西。

实际上这样还是有可能会算重。设：

/[g[n][m]=(/sum_{a+b+1=n,/max(x,y)=m}f[a][x]/times f[b][y]-/sum f[/frac{n-1}{2}][m])/div 2
/]

来进行辅助计算。

容易发现 /(g[n][m]/) 对应的任意二元组形态都不同。

先考虑用相同的 /(g[n][m]/) 填充一个集合，然后用所有的集合去填充 /(f/)。

设 /(G[n][m]/) 表示所有二元组都是 /(g[n][m]/) 集合中的元素，容易知道这个方案数是：

/[G[n][m]=/sum[x^i](/frac{1-x^{i+1}}{1-x})^{g[n][m]}=/sum/binom{i+g[n][m]-1}{i}x^{in}y^{im}
/]

然后把 /(G/) 卷起来就能得到 /(f/) 了。

复杂度相当于做一个二维半在线卷积，复杂度 /(O(n^2m^2)/) 可以通过。