可重组合是(inom{n+m-1}{m})(别问我我为什么不知道这个)
可以先考虑有根树 dp时把子节点按hash排序 相同的子树放在一起算
如果有一个重心把他当成根就行
两个重心的话还得讨论一下... 看看代码吧
#include<bits/stdc++.h>
using namespace std;
#define fp(i,l,r) for(register int (i)=(l);(i)<=(r);++(i))
#define fd(i,l,r) for(register int (i)=(l);(i)>=(r);--(i))
#define fe(i,u) for(register int (i)=front[(u)];i;i=e[i].next)
#define mem(a) memset((a),0,sizeof (a))
#define O(x) cerr<<#x<<':'<<x<<endl
#define int long long
inline int read(){
int x=0,f=1;char ch=getchar();
while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
while(isdigit(ch))x=x*10+ch-'0',ch=getchar();
return x*f;
}
void wr(int x){
if(x<0)x=-x,putchar('-');
if(x>=10)wr(x/10);
putchar('0'+x%10);
}
const int MAXN=5e5+10,Mod[2]={998244353,1e9+7},mod=1e9+7;
inline void tmod(int &x){x%=mod;}
inline int qpow(int a,int b){
int res=1;a%=mod;
for(;b;b>>=1,tmod(a*=a))
if(b&1)tmod(res*=a);
return res;
}
struct tEdge{
int v,next;
}e[MAXN<<1];
int front[MAXN],tcnt,hsh[2][MAXN],dp[MAXN][2],H[2],hsz=1e9;
int buc[MAXN],tot,sze[MAXN],ifac[MAXN],n;
inline void adde(int u,int v){
e[++tcnt]=(tEdge){v,front[u]};front[u]=tcnt;
}
void dfs1(int u,int fa){
sze[u]=1;int t=0;
fe(i,u){
int v=e[i].v;if(v==fa)continue;
dfs1(v,u);sze[u]+=sze[v];t=max(t,sze[v]);
}
t=max(t,n-sze[u]);
if(t<hsz)H[0]=u,H[1]=0,hsz=t;
else if(t==hsz)H[1]=u;
}
inline bool cmp(int x,int y){
if(hsh[0][x]==hsh[0][y])return hsh[1][x]>hsh[1][y];
return hsh[0][x]>hsh[0][y];
}
inline int color(int n,int m){
int t=ifac[m];
fd(i,n+m-1,n)tmod(t*=i);
return t;
}
void dfs(int u,int fa){
dp[u][0]=dp[u][1]=1;
fe(i,u)if(e[i].v!=fa)dfs(e[i].v,u);
tot=0;
fe(i,u)if(e[i].v!=fa)buc[++tot]=e[i].v;
sort(buc+1,buc+1+tot,cmp);
for(int l=1,r;l<=tot;l=r){
for(r=l;r<=tot&&hsh[0][buc[r]]==hsh[0][buc[l]]&&hsh[1][buc[r]]==hsh[1][buc[l]];++r);
tmod(dp[u][0]*=color(dp[buc[l]][0]+dp[buc[l]][1],r-l));
tmod(dp[u][1]*=color(dp[buc[l]][0],r-l));
}
hsh[0][u]=hsh[1][u]=3;
fp(i,0,1)fp(j,1,tot)hsh[i][u]=(hsh[i][u]*577681+7*hsh[i][buc[j]])%Mod[i];
}
main(){
n=read();
fp(i,1,n-1){
int u=read(),v=read();adde(u,v);adde(v,u);
}
dfs1(1,0);
ifac[0]=1;fp(i,1,n)ifac[i]=ifac[i-1]*i%mod;
ifac[n]=qpow(ifac[n],mod-2);fd(i,n-1,0)ifac[i]=ifac[i+1]*(i+1)%mod;
int ans=0;
if(!H[1]){
int x=H[0];
dfs(x,0);tmod(ans=dp[x][0]+dp[x][1]);
}
else{
int x=H[0],y=H[1];
dfs(x,y);dfs(y,x);
if(hsh[0][x]==hsh[0][y]&&hsh[1][x]==hsh[1][y])
tmod(ans=dp[x][0]*dp[y][1]+color(dp[x][0],2));
else tmod(ans=dp[x][0]*dp[y][0]+dp[x][1]*dp[y][0]+dp[x][0]*dp[y][1]);
}
printf("%lld
",ans);
return 0;
}