计树问题小结 version 2.0

本文接自此篇博客，旨在记录一些更有趣（？）的内容。

决定完善这篇博客是因为看见了这个题.于是便以这道题目的题解为主线写这篇blog.

(op=1,2)的时候的答案可以看上文提到的blog.

无标号有根树计数

(op=3)时的问题也就是无标号有根树的计数，在上篇blog里以烷烃计数举例，在这里考虑去掉度数限制后的做法。

记(f_i)为(i)个点的答案。考虑枚举子树大小以及该大小的子树的数量进行转移，但是复杂度过高。把转移用生成函数的形式写出来的话有：

[F(x)=xprod_{i>0}(sum_{kgeq 0}x^{ki})^{f_i}=xprod_{i>0}(frac{1}{1-x^i})^{f_i} ]

其意义如下：最前面乘的(x)表示根节点，(sum_{kgeq 0}x^{ki})表示某个大小为(i)的子树有几个，它的(f_i)次幂则对应着所有大小为(i)的子树的方案数。之后再把(k)用封闭形式丢掉。

看见这个乘积很烦人，考虑对两边去取(ln).

[ln F(x)=ln x-sum_{i>0}f_iln(1-x^i) ]

再同时求个导。

[frac{F'(x)}{F(x)}=frac{1}{x}+sum_{i>0}if_ifrac{x^{i-1}}{1-x^i} ]

去分母。

[xF'(x)=F(x)+F(x)sum_{i>0}if_ifrac{x^i}{1-x^i} ]

看起来没啥花样了？我们把(f_n)请回来：

[nf_n=f_n+sum_{i>0}f_isum_{k>0}kf_k([x^{n-i}]frac{x^k}{1-x^k}) ]

考虑一下后面那个带(x)的项是什么，由于(frac{1}{1-x^k}=sum_{igeq 0}x^{ki}),那么它再乘上(x^k)后，也只有次数是(k)的倍数的项的系数为1，于是我们得到了这样子的式子：

[nf_n=f_n+sum_{i>0}f_isum_{k>0}kf_k[k|n-i] ]

稍微整理一下，同时把下标写得更好看些：

[f_n=frac{sum_{i=1}^{n-1}f_isum_{k|n-i}kf_k}{n-1} ]

记(g_i=sum_{j|i}jf_j),得到了最终的式子：

[f_n=frac{sum_{i=1}^{n-1}f_ig_{n-i}}{n-1} ]

边界条件(f_0=0,f_1=1).

在转移的过程中求出了一个(f)的同时维护(g)，总时间复杂度(O(n^2)), 代码见下。

无标号无根树计数

思路和烷基计数差不多？

考虑已经求出了有根树的答案(f_n)，如何求无根树的答案(h_n), 主要的问题还是去掉树的形态相同但根不同的方案数。于是想到对每个形态的树钦点某个点为根。这个点最好还要和树的大小有关，不难想到钦点树的重心为根。

先考虑(n)为奇数的情况，此时每棵树有且仅有一个确定的重心，那么如果当前根不是重心的话，它一定有一个大小大于(lfloor frac{n}{2} floor)的子树，于是有：

[h_n=f_n-sum_{i= lfloor frac{n}{2} floor+1}^{n-1}f_if_{n-i} ]

接着考虑(n)为偶数的情况，稍微麻烦一点的是我们需要考虑当前树有两个重心的情况。如果只有一个重心的话我们只需要和奇数一样减去不合法的情况。而当有两个重心时，这两个点一定通过一条边相连，且把这条边断开后，只有在形成的两棵子树大小一致但形态不同时才会有多算的情况，综上所述可得计算式：

[h_n=f_n-sum_{i=frac{n}{2}+1}^{n-1}f_if_{n-i}-dbinom{f_{frac{n}{2}}}{2} ]

于是就可以做到单个的(O(1))计算了，代码如下：

int solve3()
{
	f[0]=0;f[1]=1;
	rep(i,1,n) g[i]=1;
	rep(i,2,n)
	{
		f[i]=0;
		rep(j,1,i) f[i]=add(f[i],mul(f[j],g[i-j]));
		f[i]=mul(f[i],getinv(i-1));
		int tmp=mul(f[i],i);
		for (int j=i;j<=n;j+=i) g[j]=add(g[j],tmp);
	}
	return f[n];
}

int C2(int x) {return mul(mul(x,x-1),inv2);}

int solve4()
{
	solve3();h[0]=0;h[1]=1;
	inv2=getinv(2);
	rep(i,2,n)
	{
		h[i]=0;
		rep(j,i/2+1,i-1) h[i]=add(h[i],mul(f[j],f[i-j]));
		if (i%2==0) h[i]=add(h[i],C2(f[i/2]));
		h[i]=dec(f[i],h[i]);
	}
	return h[n];
}