烷烃同分异构体数目公式？
本质上就是一个无标号无根树带度数限制的计数问题.
将问题一般化：求 n 个点的无标号无根树的个数, 且每个点的度数不超过m。
烷基 (有根树)：首先考虑计算烷基的个数 (即有根树)。
考虑暴力 DP.。设状态为 f(i,j,k)f(i,j,k)，表示当前共有 ii个点。
最大的子树大小为 jj，且根的度数为 kk。对于状态 f(i,j,k)f(i,j,k)，通过枚举最大子树的个数 l 和次大子树的大小 size。
有f(i,j,k)=∑l∑s+f(i−jl,size,k−l){s+l−1l}f(i,j,k)=∑l∑s+f(i−jl,size,k−l){s+l−1l}。
其中 s=∑ja=1∑m−1b=0f(j,a,b)s=∑a=1j∑b=0m−1f(j,a,b)。
组合数是用来可重集计数的。这是O(n3m2)O(n3m2)的。
显然可以前缀和优化，但是空间撑不住。还可以做得更好。考虑如何省掉 jj 这一维状态。即设状态为 f(i,j)f(i,j)。表示当前共有 ii 个点，根的度数为 kk。
考虑 DP 的一个技巧: 强行规定转移顺序。即，先 1...n1...n 枚举 size，表示强制用最大子树大小为 size 的情形来转移。
不妨设s=∑m−1k=0f(size,k)s=∑k=0m−1f(size,k)，那么对于一个 f(i,j)f(i,j)。
再枚举一个最大子树 (即子树大小为 size 的子树) 的个数 k。
我们便有转移f(i,j)←f(i,j)+f(i−size×k,j−k){s+k−1k}f(i,j)←f(i,j)+f(i−size×k,j−k){s+k−1k}这是 O(n2m2)O(n2m2) 的。如果是算烷基的话，便是 O(n2)O(n2) 的。
烷烃 (无根树)：只要某个点 uu 满足其子树大小都 ≤n2≤n2，那么这个点是这颗树的重心。比较显然的是, 重心最多只会有两个，并且有两个重心的情形，两个重心一定相邻。
并且另一个重心做根的时候，这个重心的子树大小为 n2n2。(当然 nn 必须要是偶数)
很多无根树同构的问题就可以通过重心转化为有根树同构。烷烃就可以这么计数。因为我们可以在 DP 烷基的时候。
强制size
