【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;
}

最新文章

  1. js高级程序设计(七)函数表达式
  2. C#日志记录函数
  3. ibatis CDATA
  4. 使用Visual Studio Code开发Asp.Net Core WebApi学习笔记(五)-- Filter
  5. Android之点击切换图片
  6. SSH连接时出现Host key verification failed的原因及解决方法
  7. WebRTC 音视频开发之路
  8. 定制textField
  9. Android-5 理解context
  10. javascript 实现禁止右键,复制,选取文本 (兼容firefox,IE,chrome等主流浏览器)
  11. ACM 刷题小技巧【转】
  12. xml中的SQL注入
  13. lightoj1234 打表技巧:分块打表
  14. 【问题与解决】怎么删除TFS云端上的项目
  15. 第6章 静态路由和动态路由(3)_RIP动态路由协议
  16. 洛谷P2605 基站选址
  17. Using KernelShark to analyze the real-time scheduler【转】
  18. Java 8 中 HashMap 的性能提升
  19. 【[AHOI2009]同类分布】
  20. 3星|麦肯锡合伙人《从1到N》:PPT讲稿,图表不错,讲解不够深入

热门文章

  1. foj Problem 2283 Tic-Tac-Toe
  2. Mysql之禁止使用索引
  3. 容器 What, Why, How
  4. [转]结队开发之多storyboard
  5. PHP读取APK的包信息,包括包名,应用名,权限,LOGO等
  6. FFT题集
  7. css查缺补漏2
  8. QBXT T15565 Day4上午道路分组
  9. Java过滤HTML标签工具类
  10. squirrelsql安装