题目链接：

题意：给出一个n个节点的树，有m种颜色。问不同的染色方案有多少？

 

思路：本题首先要解决的就是对称的情况怎么办，找到树的中心，也就是找到树上的一条最长路，最长路为奇数，则中间一个节点作为根节点，否则，在中间增加一个节点作为根节点使得两边的最长路相等。然后就是树形DP，ans[u]表示以u为根节点的子树的总的染色方案，hash[u]存储以u为根节点的子树的结构。设u节点有k个子节点,v1,v2……vk，首先将子节点按照hash值排序，这样，同构的子树在排序后就会相邻，设有x个子树同构，则这x个子树总的染色方案为C(ans[v]+x-1,x)。接着就是将这些相乘就得到u节点的ans值，u节点的hash值由子节点的hash值Hash得到。

 

#include 
     
       #include 
      
        #include 
       
         #include 
        
          using namespace std;  struct node {     int v,next; };  struct Node {     __int64 hash,ans; };   const __int64 mod=1000000007; const __int64 P=10003; const __int64 Q=100000037; node edges[200005]; Node q[50005]; int head[50005],e,E,M,MM,C,f[50005],dp[50005],n; __int64 hash[100005],ans[100005],p[100005],son[50005];  void Add(int u,int v) {     edges[e].v=v;     edges[e].next=head[u];     head[u]=e++; }  __int64 POW(__int64 a,__int64 b) {     __int64 ans=1;     while(b)     {         if(b&1) ans=(ans*a)%mod;         a=(a*a)%mod;         b>>=1;     }     return ans; }  __int64 cal(int n,int m) {     if(n==m) return 1;     __int64 n1=1,n2=p[m],i;     for(i=1;i<=m;i++) n1=n1*(n-i+1)%mod;     return n1*POW(n2,mod-2)%mod; }  int cmp(Node a,Node b) {     return a.hash
         
          m1) m2=m1,m1=t,f[u]=i;         else if(t>m2) m2=t;     }     if(M
          
           M+1) MM=edges[f[MM]].v; E=f[MM]; Add(MM,n+1); Add(n+1,MM); Add(edges[f[MM]].v,n+1); Add(n+1,edges[f[MM]].v); MM=n+1; ans[MM]=1; } else { E=0; while(dp[MM]*2>M) MM=edges[f[MM]].v; ans[MM]=C; } DFS1(MM,-1); printf("%I64d\n",ans[MM]); } return 0; }