数独立集显然是可以树形dp的，问题在于本质不同。
假设已经给树确立了一个根并且找到了所有等效（注意是等效而不是同构）子树，那么对转移稍加修改使用隔板法就行了。
关键在于找等效子树。首先将树的重心（若有两个则加一个点作为唯一重心）作为根。这样任意极大等效子树（比如某两个等效子树里面的一部分等效，那么里面这一部分就不是极大的）一定有相同的父亲，否则我们所选的根是肯定存在一棵子树大小大于树的一半的，与重心性质矛盾。那么判等效就只需要考虑子树内同构了。
同构判断采取哈希。这里使用最简单的类似字符串哈希的做法，用子树大小哈希。在保证同构树哈希值相同的前提下尽量增加变数。
#include<iostream> #include<cstdio> #include<cmath> #include<cstdlib> #include<cstring> #include<algorithm> using namespace std; int read() { int x=0,f=1;char c=getchar(); while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();} while (c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar(); return x*f; } #define N 500010 #define P 1000000007 #define ul unsigned long long int n,p[N],p_new[N],f[N][2],size[N],q[N],inv[N],root,t=0; ul hash[N]; struct data{int to,nxt; }edge[N<<1],edge_new[N<<1]; void addedge(int x,int y){t++;edge[t].to=y,edge[t].nxt=p[x],p[x]=t;} void addedge_new(int x,int y){t++;edge_new[t].to=y,edge_new[t].nxt=p_new[x],p_new[x]=t;} void dfs(int k,int from) { size[k]=1; for (int i=p[k];i;i=edge[i].nxt) if (edge[i].to!=from) { dfs(edge[i].to,k); size[k]+=size[edge[i].to]; } } void dfs2(int k,int from) { for (int i=p[k];i;i=edge[i].nxt) if (edge[i].to!=from) { addedge_new(k,edge[i].to); dfs2(edge[i].to,k); } } int findroot(int k,int from) { int mx=0; for (int i=p[k];i;i=edge[i].nxt) if (edge[i].to!=from&&size[edge[i].to]>size[mx]) mx=edge[i].to; if ((size[mx]<<1)<=n) return k; else return findroot(mx,k); } int C(int n,int m) { int ans=1; for (int i=n;i>=n-m+1;i--) ans=1ll*ans*i%P; return 1ll*ans*inv[m]%P; } bool cmp(const int&a,const int&b) { return hash[a]<hash[b]; } void gethash(int k) { int cnt=0; for (int i=p[k];i;i=edge[i].nxt) q[++cnt]=hash[edge[i].to]; sort(q+1,q+cnt+1); for (int i=1;i<=cnt;i++) hash[k]=hash[k]*107+q[i]; hash[k]=(hash[k]*509+size[k])%P; } void dp(int k) { for (int i=p[k];i;i=edge[i].nxt) dp(edge[i].to),gethash(edge[i].to); int cnt=0; for (int i=p[k];i;i=edge[i].nxt) q[++cnt]=edge[i].to; sort(q+1,q+cnt+1,cmp); f[k][0]=f[k][1]=1; for (int i=1;i<=cnt;i++) { int t=i; while (t<cnt&&hash[q[t+1]]==hash[q[i]]) t++; f[k][1]=1ll*f[k][1]*C(f[q[i]][0]+t-i,t-i+1)%P; f[k][0]=1ll*f[k][0]*C(f[q[i]][0]+f[q[i]][1]+t-i,t-i+1)%P; i=t; } } int main() { #ifndef ONLINE_JUDGE freopen("bzoj3162.in","r",stdin); freopen("bzoj3162.out","w",stdout); const char LL[]="%I64d "; #else const char LL[]="%lld "; #endif n=read(); inv[0]=inv[1]=1;for (int i=2;i<=n;i++) inv[i]=P-1ll*(P/i)*inv[P%i]%P; for (int i=2;i<=n;i++) inv[i]=1ll*inv[i]*inv[i-1]%P; for (int i=1;i<n;i++) { int x=read(),y=read(); addedge(x,y),addedge(y,x); } dfs(1,1); root=findroot(1,1); dfs(root,root); int v=0; for (int i=p[root];i;i=edge[i].nxt) if (!(n&1)&&size[edge[i].to]==(n>>1)) {v=edge[i].to;break;} t=0; if (v) { n++;dfs2(root,v);dfs2(v,root); addedge_new(n,root),addedge_new(n,v);root=n; } else dfs2(root,root); memcpy(p,p_new,sizeof(p)); memcpy(edge,edge_new,sizeof(edge)); dfs(root,root); dp(root); if (v) { int x=edge[p[root]].to,y=edge[edge[p[root]].nxt].to; if (hash[x]==hash[y]) f[root][0]=(C(f[x][0]+1,2)+1ll*f[x][0]*f[x][1]%P)%P; else f[root][0]=(1ll*f[x][0]*(f[y][0]+f[y][1])%P+1ll*f[x][1]*f[y][0]%P)%P; f[root][1]=0; } cout<<(f[root][0]+f[root][1])%P; return 0; }