BZOJ 3162 独钓寒江雪(树同构计数)

给定一棵无根树，求其中本质不同的独立集的个数。
无根树同构。
转化成以重心为根的有根树，如果重心有两个，就在这两个重心之间插入一个点与这两个重心连边，这个点作为新的重心。
然后就成了有根树同构过程树形DP。
这个DP非常naive就不介绍了。
如果子树有$k$个同构，他们的方案数都是$p$
那么我们要本质不同的方案分配，可以想到令给子树分配方案的编号不递减，那么就是每分配给前一个子树一个方案，就要在后面加一个新点来让后面的子树可以和前面的选同一个方案，所以为$\left(\genfrac{}{}{0ex}{}{p+k-1}{k}\right)$
$\mathrm{A}\mathrm{C}\mathrm{C}\mathrm{o}\mathrm{d}\mathrm{e}$

#pragma GCC optimize(3)
#include<bits/stdc++.h>
#define maxn 500005
#define mod 1000000007
#define LL long long
#define pb push_back
#define pii pair<LL,int>
#define mp make_pair
#define S 131
using namespace std;

int Pow(int base,int k){ 
   
	int ret = 1;
	for(;k;k>>=1,base=1ll*base*base%mod)
		if(k&1)
			ret=1ll*ret*base%mod;
	return ret;
}

char cb[1<<16],*cs=cb,*ct=cb;
#define getc() (cs==ct&&(ct=(cs=cb)+fread(cb,1,1<<16,stdin),cs==ct)?0:*cs++)
void read(int &res){ 
   
	char ch;
	for(;!isdigit(ch=getc()););
	for(res=ch-'0';isdigit(ch=getc());res=res*10+ch-'0');
}
int n,m,f[maxn][2],siz[maxn];
LL h[maxn];
vector<int>G[maxn],rt;
int Min = 0x3f3f3f3f;
void dfs0(int u,int ff){ 
   
	int Mx = 0;
	siz[u] = 1;
	for(int i=0,v;i<G[u].size();i++)
		if((v=G[u][i])!=ff){ 
   
			dfs0(v,u);
			siz[u] += siz[v];
			Mx = max(Mx , siz[v]);
		}
	Mx = max(Mx , n - siz[u]);
	if(Mx < Min) 
		Min = Mx , rt.clear();
	if(Mx == Min) rt.pb(u);
}
inline bool cmp(const int &u,const int &v){ 
   
	return h[u] < h[v];
}
int invf[maxn];
int C(int n,int m){ 
   
	int ret = 1;
	for(int i=1;i<=m;i++)
		ret = 1ll * ret * (n-i+1) % mod;
	return 1ll * ret * invf[m] % mod;
}
void dfs1(int u,int ff){ 
   
	for(int i=0;i<G[u].size();i++)
		if(G[u][i] == ff){ 
   
			if(i!=G[u].size()-1)
				swap(G[u][i],G[u].back());
			G[u].pop_back() , i--;
		}
		else dfs1(G[u][i],u);
	sort(G[u].begin(),G[u].end(),cmp);
	h[u] = 3214;
	f[u][0] = f[u][1] = 1;
	for(int i=0,j=0;i<G[u].size();i=j){ 
   
		for(j=i;j<G[u].size() && h[G[u][j]] == h[G[u][i]];j++)
			h[u] = ((h[u] * S) ^ h[G[u][j]]);
		f[u][0] = 1ll * f[u][0] * C((f[G[u][i]][0]+f[G[u][i]][1]+j-i-1) % mod,j-i) % mod;
		f[u][1] = 1ll * f[u][1] * C(f[G[u][i]][0]+j-i-1,j-i) % mod;
	}
	h[u] *= 1ll * S * S * S;
}

int main(){ 
   
	//freopen("1.in","r",stdin);
	read(n);
	invf[0] = invf[1] = invf[n] = 1;
	for(int i=1;i<=n;i++) invf[n] = 1ll * invf[n] * i % mod;
	invf[n] = Pow(invf[n] , mod-2);
	for(int i=n-1;i>=2;i--) invf[i] = 1ll * invf[i+1] * (i+1) % mod;
	for(int i=1,u,v;i<n;i++){ 
   
		read(u),read(v);
		G[u].pb(v),G[v].pb(u);
	}
	dfs0(1,0);
	int r = rt[0];
	if(rt.size() == 2){ 
   
		for(int i=0;i<G[rt[0]].size();i++)
			if(G[rt[0]][i] == rt[1]){ 
   
				if(G[rt[0]].size()-1 != i) swap(G[rt[0]][i],G[rt[0]].back());
				G[rt[0]].pop_back();
			}
		for(int i=0;i<G[rt[1]].size();i++)
			if(G[rt[1]][i] == rt[0]){ 
   
				if(G[rt[1]].size()-1 != i) swap(G[rt[1]][i],G[rt[1]].back());
				G[rt[1]].pop_back();
			}
		G[++n].pb(rt[0]),G[n].pb(rt[1]);
		r = n;
	}
	dfs1(r,0);
	printf("%lld\n",(f[r][0] + (rt.size()==1 ? f[r][1] : -(h[rt[0]] == h[rt[1]] ? C(f[rt[0]][1]+1,2) : f[rt[0]][1] * 1ll * f[rt[1]][1] % mod)) % mod + mod) % mod);
}