源于一节化学课的思想跳跃

化学课终于教到有机了，第一次知道什么是甲烷

看到烷烃的结构，尼玛这不就是棵树嘛

化学老师也是闲，叫我们来推推戊烷己烷的同分异构体个数

这对一个有OI基础的人来说基本不难

然后就顺势想到了如何编程求烷烃的同分异构体个数

心想着：这毕竟是一棵树啊，树的话OI就能考。。。

激动万分

然而想了想发现自己连口胡算法都不会。。。

为自己的智商感动得泪流满面

下课上网找题解，抱着不大的希望在BZOJ搜索了下Chemistry，就找到原题了

泪流满面，然而才8人A，其中大部分都是打表的。。。

找到ACM原题也没能找到题解。。。我擦勒

问了下Claris，知道了貌似要枚举树重心去DP一发。。。听都没听过的新思路

维基搜了下，没找到公式，OEIS的列表倒是有一点用（别跟我说公式其实就藏在OEIS下面一堆英文中QwQ

还找到了范浩强神犇的Blog，解法也是与重心有关，然而题解的网站挂了。。。

我擦勒什么题解都没有，而且听到算法梗概就觉得已经超出了我的思考能力了

泪流满面

然后隔没多久，接触到了有根树无根树的计数方法

我擦勒无根树计数不就是和求烷烃的数量啊

想了想，度数限制不大于4。。。感动

接下来就是一系列不服输的行为了

照着公式乱啃找计数和去重原理，自己琢磨出度数限制的方案

两节理综荒废，最后推出了一个什么鬼的递推公式。。。

上机实验，发现各种错误，在草稿纸上改公式啊改公式

我还把35种壬烷都画了出来。。。

然后弄出了个$O(n^3)$的算法，顺利过掉ACM的$N\le50$规模

BZOJ的$N\le500$由于高精度和算法复杂度太大，最慢9s

睡觉的时候才发现自己硬是把$O(n^2)$的算法写成$O(n^3)$

智商感人

思路就是用背包DP计算满足度数限制（每个点的度数不大于4）的有根树的数量

然后去重计算满足度数限制的无根树的数量

原理类似普通有根树和无根树的计数原理，建议结合看

#include <cstdio>
#include <algorithm>

#define rep(i, l, r) for(int i=l; i<=r; i++)
#define down(i, l, r) for(int i=l; i>=r; i--)
#define clr(x, c) memset(x, c, sizeof(x))
#define travel(x) for(edge *p=fir[x]; p; p=p->n)
#define pb push_back
#define ll long long
#define ull unsigned long long

#define maxn 501
#define maxl 29
#define mx 100000000
#define inf 0x7fffffff

using namespace std;
inline int read()
{
	int x=0, f=1; char ch=getchar();
	while (ch<'0' || ch>'9') {if (ch=='-') f=-1; ch=getchar();}
	while ('0'<=ch && ch<='9') x=x*10+ch-'0', ch=getchar();
	return x*f;
}

struct node{int v[maxl], l;} f[maxn], k[maxn], h[maxn], g[5][maxn], sum, I, Nul, m[5];
int n, T; ll tmpc[maxl];

inline void Add(node &a, node b)
{
	rep(i, 0, b.l-1) a.v[i]+=b.v[i];
	a.l=max(a.l,b.l);
	rep(i, 0, a.l-1) if (a.v[i]>=mx) a.v[i+1]+=a.v[i]/mx, a.v[i]%=mx;
	while (a.v[a.l]!=0) 
	{
		if (a.v[a.l]>=mx) a.v[a.l+1]+=a.v[a.l]/mx, a.v[a.l]%=mx;
		a.l++;
	}
}

inline void Sub(node &a, node b)
{
	rep(i, 0, a.l-1) a.v[i]-=b.v[i];
	rep(i, 0, a.l-1) while (a.v[i]<0) a.v[i+1]--, a.v[i]+=mx;
	while (a.v[a.l-1]==0 && a.l>1) a.l--;
}

inline void Add(node &a)
{
	a.v[0]++;
	rep(i, 0, a.l-1) if (a.v[i]>=mx) a.v[i+1]+=a.v[i]/mx, a.v[i]%=mx; else return;
	while (a.v[a.l]!=0) 
	{
		if (a.v[a.l]>=mx) a.v[a.l+1]+=a.v[a.l]/mx, a.v[a.l]%=mx;
		a.l++;
	}
}

inline node Sub(node a)
{
	a.v[0]--;
	rep(i, 0, a.l-1) if (a.v[i]<0) a.v[i+1]--, a.v[i]+=mx; else return a;
	while (a.v[a.l-1]==0 && a.l>1) a.l--;
	return a;
}

inline node Div(node a, int x)
{
	int tmp=0;
	down(i, a.l-1, 0) tmp=tmp*mx+a.v[i], a.v[i]=tmp/x, tmp%=x;
	while (a.v[a.l-1]==0 && a.l>1) a.l--;
	return a;
}

node operator * (node a, node b)
{
	node c=Nul; c.l=a.l+b.l-1;
	//clr(tmpc,0); 
	rep(i, 0, c.l) tmpc[i]=0;
	rep(i, 0, a.l-1) rep(j, 0, b.l-1) tmpc[i+j]+=1LL*a.v[i]*b.v[j];
	
	rep(i, 0, c.l-1) if (tmpc[i]>=mx) tmpc[i+1]+=tmpc[i]/mx, c.v[i]=tmpc[i]%mx; else c.v[i]=tmpc[i];
	while (tmpc[c.l]!=0) 
	{
		if (tmpc[c.l]>=mx) tmpc[c.l+1]=tmpc[c.l]/mx, c.v[c.l]=tmpc[c.l]%mx; else tmpc[c.l+1]=0, c.v[c.l]=tmpc[c.l];
		c.l++;
	}
	return c;
}

node C(node x, int y)
{
	node now=I;
	rep(i, 1, y) now=now*x, Add(x);
	rep(i, 1, y) now=Div(now,i);
	return now;
}

inline void Put(node &a)
{
	printf("%d", a.v[a.l-1]);
	down(i, a.l-2, 0) printf("%08d", a.v[i]);
}

int main()
{
	n=read();
	I.l=1; I.v[0]=1;
	f[1]=k[1]=h[1]=I; rep(o, 0, 4) g[o][o]=I;
	rep(a, 2, n)
	{
		//printf("%d %d\n", a, T);
		sum=Nul;
		rep(o, 1, 3) Add(sum,g[o][a-1]);
		f[a]=sum;
		
		Add(sum,g[4][a-1]);
		rep(c, 1, 4) if (a*c<=n) m[c]=C(f[a],c);
		
		down(o, 4, 1) rep(c, 1, o) rep(i, a*c+o-c, n-1) if (g[o-c][i-a*c].l!=0)
		{
			node &A=g[o][i], B=g[o-c][i-a*c]*m[c];
			rep(i, 0, B.l-1) A.v[i]+=B.v[i];
			A.l=max(A.l,B.l);
			rep(i, 0, A.l-1) if (A.v[i]>=mx) A.v[i+1]+=A.v[i]/mx, A.v[i]%=mx;
			while (A.v[A.l]!=0) 
			{
				if (A.v[A.l]>=mx) A.v[A.l+1]+=A.v[A.l]/mx, A.v[A.l]%=mx;
				A.l++;
			}
		}
		k[a]=sum;
		
		rep(i, 1, (a-1)/2) if (i!=a-i) Sub(sum,f[i]*f[a-i]);
		if (a%2==0) Sub(sum,Div(f[a/2]*Sub(f[a/2]),2));
		h[a]=sum;
	}
	Put(h[n]);
    return 0;
}

有老司机知道枚举重心DP的做法么。。。现在依旧不知道QwQ

update 16.01.10:

后来在书中翻到了一句话：

假如两棵无根树同构，那么以各自的重心作为根的有根树也同构

也许这就是正解了。。。

有根树背包DP的时候只要使得子树大小小于$\frac n2$就行了

748ms AC

一些链接：

OEIS序列

范浩强Blog——烷烃同分异构体个数的计算

ACM原题