题意是求一棵无根树本质不同独立集的个数

那个所谓“极寒点”的选取就是独立集。

结构相同就是树同构,完全相同就是树的形态和独立集都相同。

我们先求出树的重心,就可以转化为有根树同构问题。

令$f[u][1]$为在$u$的子树中,选取$u$的方案树,$f[u][0]$为在$u$的子树中,不选取$u$的方案数。

得到最基本的DP方程：

$f[u][0]=\prod_{v\in\;son(u)}(f[v][0]+f[v][1])$

$f[u][1]=\prod_{v\in\;son(u)}f[v][0]$

但是可能出现直径长为奇数的情况,需要分类讨论。

判断树同构用哈希乱搞就好了。

1 #include 
      
         2 #include 
       
          3 #include 
        
           4 #include 
         
            5 using namespace std;  6 #define maxn 500010  7 #define mod 1000000007  8 #define p1 2150527  9 #define p2 1231231237 10 #define LL long long 11 inline int read() 12 { 13     int s=0,f=1; 14     char ch=getchar(); 15     while(ch<'0'||ch>'9') 16     { 17         if(ch=='-') 18             f=-1; 19         ch=getchar(); 20     } 21     while(ch>='0'&&ch<='9') 22         s=s*10+ch-'0',ch=getchar(); 23     return s*f; 24 } 25 struct edge 26 { 27     int u,v,nex; 28 }e[maxn<<1]; 29 int pr[maxn],cnt=1; 30 int siz[maxn]; 31 void add(int u,int v) 32 { 33     e[++cnt]=(edge){u,v,pr[u]}; 34     pr[u]=cnt; 35     e[++cnt]=(edge){v,u,pr[v]}; 36     pr[v]=cnt; 37 } 38 int rt[2],root; 39 LL inv[maxn]; 40 LL haha[maxn]; 41 LL f[maxn][2]; 42 int st[maxn]; 43 bool cmp(int a,int b) 44 { 45     return haha[a]
          
           1;m--) 51         ans=ans*(n-m+1)%mod*inv[m]%mod; 52     return ans; 53 } 54 void dp(int u,int fa) 55 { 56     int top=0,i,j; 57     haha[u]=20010416; 58     for(i=pr[u];i;i=e[i].nex) 59         if(e[i].v!=fa) 60             dp(e[i].v,u); 61     for(i=pr[u];i;i=e[i].nex) 62         if(e[i].v!=fa) 63             st[++top]=e[i].v; 64     sort(st+1,st+top+1,cmp); 65     f[u][0]=f[u][1]=1; 66     for(i=1;i<=top;i=j) 67     { 68         for(j=i+1;j<=top;j++) 69             if(haha[st[i]]!=haha[st[j]]) 70                 break; 71         f[u][0]=f[u][0]*C((j-i-1+f[st[i]][0]+f[st[i]][1])%mod,j-i)%mod; 72         f[u][1]=f[u][1]*C((j-i-1+f[st[i]][0])%mod,j-i)%mod; 73     } 74     for(i=1;i<=top;i++) 75         haha[u]=haha[u]*p1+(haha[st[i]]+i)*p2; 76 } 77 int n; 78 void dfs(int u,int fa) 79 { 80     bool flag=1; 81     siz[u]=1; 82     int i,v; 83     for(i=pr[u];i;i=e[i].nex) 84     { 85         v=e[i].v; 86         if(v!=fa) 87         { 88             dfs(v,u); 89             if((siz[v]<<1)>n) 90                 flag=0; 91             siz[u]+=siz[v]; 92         } 93     } 94     if((siz[u]<<1)