無标号樹的計數原理（組合計數，背包問題，隔闆法，樹的重心）

閑話

一個計數問題入門級選手來搞這種東西

最初的動力來自高一化學課有機物（滑稽）。《同步導練》出了個這樣的選擇題。

一個結構極其龐大的烷烴（二十幾個碳原子），求它的主鍊長度。

這不是個求樹的直徑的裸題麼？！OI選手掃兩眼就出來了，然而别的同學費勁心思找完了還是錯的。

于是第一次在正常課中體驗到作為OIer的優越感。。。。。。

又是一節課，芙蓉姐開始要我們畫己烷、庚烷的同分異構體？！

這不是等于要求節點數為\(n\)，點度數不超過\(4\)的無标号的無根樹個數嗎？沒見過，但還是有一點DP思想，蒟蒻開始手動枚舉直徑，不一會兒也畫出來了。

下課以後問芙蓉姐有沒有公式。“這個東西要靠計算機知識來推導啦！”

又一次在正常課中體驗到作為OIer的優越感。。。。。。

無标号有根樹計數

就是有多少種\(n\)個點，每個點度數限制為\(m\)的不同形态的無根樹。比如說求烷基就是度數限制為\(4\)的有根樹（那個未配對的鍵當成根就行了）。

放__debug大佬的部落格（戳這裡）

叉姐過來的時候也聊了聊這個有趣的東西。

先設\(f_{i,j}\)為\(i\)個點，根節點度數為\(j\)的方案數。顯然\(\sum\limits_{j=0}^mf_{n,j}\)就是答案。

再設\(a_i=\sum\limits_{j=0}^{m-1}f_{i,j}\)。這是個子樹背包轉移過程中的狀态量，去掉\(f_{i,m}\)是因為在樹中隻有根能有\(m\)個子節點，而其它點都被父節點占去了一個點度。

引入一個Trick：

如果把樹（除根以外）分成若幹部分，每個部分都由\(k_s\)個大小為\(s\)的子樹構成，那麼這一部分的方案數是\(\binom{a_s+k_s-1}{k_s}\)

這個要用隔闆法解釋。

簡要介紹一下隔闆法——把\(n\)個物品分成\(m\)段的方案數為\(\binom{n+m-1}{m-1}\)（允許有的段為空）

證明的話，可以把分成\(m\)段看成在物品序列中插入\(m-1\)個隔闆，相鄰隔闆（或隔闆與序列末端）間就是一段。也就等于有長度為\(n+m-1\)的序列，欽定其中\(m-1\)個為隔闆，剩下\(n\)個就是物品了。

\(k\)個子樹中，直接欽定每一個選什麼，我們并不能計數。是以要運用逆向思維，把\(k\)個子樹分成\(a_s\)組，每一組對應一種形态（仔細想想）。這樣方案數就可以輕易地寫出來了，為\(\binom{a_s+k_s-1}{a_s-1}\)。然而\(a_s\)很大，是以在計算過程中一般寫\(\binom{a_s+k_s-1}{k_s}\)

然後求和可以寫成這種很不靠譜的式子

\[f_{i,j}=\sum_{k_1+2k_2+...+jk_j=i}\prod_{s=1}^j\binom{a_s+k_s-1}{k_s}

\]

這個樣子要怎麼統計才好呢？

利用DP中的常用思想，保證轉移的有序性，我們可以限制轉移中出現的最大子樹大小\(mx\)，再用背包進行轉移。具體來說，先從小到大枚舉\(mx\)，對于每一個\(i,j\)，我們可以枚舉大小為\(mx\)的子樹個數\(k\)，從\(f_{i-k\cdot mx,j-k}\)處轉移，方程為

\[f_{i,j}\leftarrow \sum_{k=1}^{\max\{j,\lfloor\frac i{mx}\rfloor\}}f_{i-k\cdot mx,j-k}\binom{a_{mx}+k-1}{k}

試想一下，因為對于每一種情況，最大的子樹大小及其個數是唯一的，是以我們就做到了不重不漏。

算上階乘需要的時間，複雜度大概是\(O(n^2m\log m)\)的樣子。如果是烷基，\(m\)是常數，複雜度就是\(O(n^2)\)

題目

LOJ6185 烷基計數

然而組合數要取模，不知如何是好。交過這題的Dalao們似乎有另一種優秀的做法？蒟蒻再去學習學習。

無标号無根樹計數

驚奇地發現__debug巨佬最初跟我想的一樣，枚舉直徑，轉而枚舉直徑的一半進行轉移，然而是個\(O(n^4)\)的垃圾算法（貌似字首和一下可以優化到\(O(n^3)\)？）

然後就知道了要去對以重心為根的有根樹計數。好有道理啊！因為重心在樹中（至少在奇數個點的樹中）是唯一的。

問題就轉化為有根樹計數。隻有兩個地方不一樣。一個是為了保證最後的根是重心，我們強制\(mx<\lceil\frac n 2\rceil\)。另一個是由前一個引出的，因為假如\(n\)為偶數，那麼可能會有兩個重心。這兩個重心的子樹大小都是\(\frac n 2\)，是以沿用上面那個隔闆法式子就好了。最終結果的方程為

\[ans=\sum_{j=0}^{m}f_{n,j}+[n\bmod2=0]\binom{a_{\frac n 2}+1}2

[BZOJ4271]chemistry（可以去這裡交）

[Tsinsen1287]數樹（點選進入題目）

然而都需要寫高精度。。。。。。

第二個就是點數為\(\frac{n-2}{m-1}\)度數為\(m\)的無根樹計數，可以了解為把葉子節點都去掉

然而\(n=6002\)太喪了，連__debug巨佬的python都要跑10s的樣子。我再去給高精度卡常估計也沒什麼用了。生成函數是什麼？置換群是什麼？以後再填坑吧！

第一個的代碼

#include<iostream>
using namespace std;
//高精度太長了不粘了，可以看蒟蒻以前的blog，也可以套個其它的版子進來
const int N=509,m=4;
bign f[N][N];
inline bign C(RG bign n,RG int m){
	RG bign ret=n;RG int i;
	for(i=m;i>1;--i)ret*=--n;
	for(i=m;i>1;--i)ret/=i;
	return ret;
}
int main(){
	f[1][0]=1;//初值
	RG int n,i,j,k,mx;
	RG bign a,ans;
	cin>>n;
	for(mx=1;mx<(n+1)>>1;++mx){//枚舉限制
		for(a=j=0;j<m;++j)
			a+=f[mx][j];//預處理a
		for(i=n;i>mx;--i)//從大到小，防止重複計數
			for(j=1;j<=m;++j)
				for(k=1;k<=j&&mx*k<i;++k)
					f[i][j]+=f[i-mx*k][j-k]*C(a+k-1,k);
	}
	for(ans=j=0;j<=m;++j)
		ans+=f[n][j];
	if(!(n&1)){//特判雙重心
		for(a=j=0;j<m;++j)
			a+=f[n>>1][j];
		ans+=C(++a,2);
	}
	cout<<ans<<endl;
	return 0;
}