【BZOJ3162】独钓寒江雪 树同构+DP

【BZOJ3162】独钓寒江雪

题解：先进行树hash，方法是找重心，如果重心有两个，则新建一个虚点将两个重心连起来，新点即为新树的重心。将重心当做根进行hash，hash函数不能太简单，我的方法是：将x的所有儿子的hash值排序，然后将这些hash值立方合在一起作为x的hash值。

进行完树hash后，我们考虑DP。首先不考虑同构，设f[0/1][x]表示选（不选）x时，在x的子树中选出独立集的方案数，则有

$f[0][x]=\prod f[1][y]+f[0][y]\\f[1][x]=\prod f[0][y]$

考虑同构，如果x有m个儿子是相同的，它们的f值都是s，那么可以转化成如下问题：给m个相同球染s种颜色有多少种方案，显然答案=$C_{m+s-1}^m$。

如果根是虚点，那么最后统计答案的时候需要特判。

#include <cstdio>

#include <iostream>

#include <cstring>

#include <algorithm>

#include <vector>

using namespace std;

typedef unsigned long long ull;

typedef long long ll;

const int maxn=500010;

const ll mod=1000000007;

int n,rt,rt1,rt2,cnt;

int head[maxn],next[maxn<<1],to[maxn<<1],siz[maxn];

bool vis[maxn];

ull hs[maxn];

ll f[2][maxn],ine[maxn],jcc[maxn];

vector<int> ch[maxn];

bool cmp(int a,int b)

{

	return hs[a]<hs[b];

}

inline int rd()

{

	int ret=0,f=1;	char gc=getchar();

	while(gc<'0'||gc>'9')	{if(gc=='-')f=-f;	gc=getchar();}

	while(gc>='0'&&gc<='9')	ret=ret*10+gc-'0',gc=getchar();

	return ret*f;

}

void findr(int x,int fa)

{

	siz[x]=1;

	int flag=0;

	for(int i=head[x];i!=-1;i=next[i])	if(to[i]!=fa)	findr(to[i],x),siz[x]+=siz[to[i]],flag|=(siz[to[i]]>(n/2));

	flag|=(n-siz[x]>(n/2));

	if(!flag&&rt1)	rt2=x;

	if(!flag&&!rt1)	rt1=x;

}

void add(int a,int b)

{

	to[cnt]=b,next[cnt]=head[a],head[a]=cnt++;

}

void gethash(int x)

{

	for(int i=head[x];i!=-1;i=next[i])	if(!vis[to[i]])	vis[to[i]]=1,ch[x].push_back(to[i]);

	hs[x]=ch[x].size()+1;

	if(!ch[x].size())	return ;

	for(int i=0;i<(int)ch[x].size();i++)	gethash(ch[x][i]);

	sort(ch[x].begin(),ch[x].end(),cmp);

	for(int i=0;i<(int)ch[x].size();i++)	hs[x]=hs[x]*131+hs[ch[x][i]]*hs[ch[x][i]]*hs[ch[x][i]];

}

ll calc(ll a,ll b)

{

	ll ret=1;

	for(ll i=a;i>a-b;i--)	ret=ret*i%mod;

	return ret*jcc[b]%mod;

}

void dfs(int x)

{

	f[0][x]=1,f[1][x]=1;

	ll now=0;

	for(int i=0,j;i<(int)ch[x].size();i++)

	{

		j=ch[x][i],dfs(j);

		now++;

		if(i==(int)ch[x].size()-1||hs[j]!=hs[ch[x][i+1]])

		{

			f[0][x]=f[0][x]*calc(now+f[1][j]+f[0][j]-1,now)%mod;

			f[1][x]=f[1][x]*calc(now+f[0][j]-1,now)%mod;

			now=0;

		}

	}

}

int main()

{

	n=rd();

	int i,a,b;

	memset(head,-1,sizeof(head));

	ine[1]=jcc[1]=1;

	for(i=2;i<=n;i++)	ine[i]=(mod-(mod/i)*ine[mod%i]%mod)%mod,jcc[i]=jcc[i-1]*ine[i]%mod;

	for(i=1;i<n;i++)	a=rd(),b=rd(),add(a,b),add(b,a);

	findr(1,0);

	if(rt2)	add(++n,rt1),add(n,rt2),rt=n;

	else	rt=rt1;

	vis[rt]=1,gethash(rt);

	dfs(rt);

	if(rt2)

	{

		if(hs[rt1]==hs[rt2])	printf("%lld",(f[0][rt1]*(f[0][rt1]+1)/2+f[0][rt1]*f[1][rt2])%mod);

		else	printf("%lld",(f[0][rt]-f[1][rt1]*f[1][rt2]%mod+mod)%mod);

	}

	else	printf("%lld",(f[0][rt]+f[1][rt])%mod);

	return 0;

}