考虑如果边 /((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)/) 可以通过。
原创文章，作者：ItWorker，如若转载，请注明出处：https://blog.ytso.com/tech/pnotes/289391.html