HDU 4275 Color the Tree(트 리 동 구성)

제목 링크:http://acm.hdu.edu.cn/showproblem.php?pid=4275
제목:n 개 노드 의 나 무 를 주 고 m 가지 색상 이 있 습 니 다.--다른 염색 방안 은 얼마나 되 나.
 
사고:본 문 제 는 먼저 대칭 적 인 상황 을 해결 해 야 한다.인터넷 에서 나무의 중심 을 찾 아야 한다 고 말 했다.즉,나무의 가장 긴 길 을 찾 는 것 이다.가장 긴 길 은 홀수 이 고 중간 에 한 노드 를 뿌리 노드 로 한다.그렇지 않 으 면 중간 에 한 노드 를 추가 하여 뿌리 노드 로 서 양쪽 의 가장 긴 길 을 똑 같이 한다.그 다음 에 나무 형 DP,ans[u]는 u 를 뿌리 노드 로 하 는 서브 트 리 의 전체적인 염색 방안 을 나타 내 고 hash[u]는 u 를 뿌리 노드 로 하 는 서브 트 리 의 구 조 를 저장 합 니 다.u 노드 를 설정 하면 k 키 노드,v1,v2...vk 가 있 습 니 다.먼저 하위 노드 를 hash 값 에 따라 정렬 합 니 다.그러면 같은 구조의 하위 나 무 는 정렬 한 후에 인접 합 니 다.x 키 트 리 와 같은 구 조 를 설정 하면 이 x 키 트 리 의 전체적인 염색 방안 은 C(ans[v]+x-1,x)입 니 다.이 식 이 어떻게 밀어 내 는 지 저도 잘 모 르 겠 습 니 다.어쨌든 ans[v]=2,x=2 를 시험 해 본 것 이 옳 습 니 다.그 다음 에 이 를 곱 하면 u 노드 의 ans 값 을 얻 고 u 노드 의 hash 값 은 하위 노드 의 hash 값 Hash 에서 얻 을 수 있 습 니 다.
 

 #include <iostream>

 #include <algorithm>

 #include <cstdio>

 #include <cstring>

 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<b.hash;

 }

 

 

 void init()

 {

     int i;

     p[1]=1;

     for(i=2;i<=100000;i++) p[i]=p[i-1]*i%mod;

 }

 

 

 int DFS(int u,int pre)

 {

     int m1=0,m2=0,i,v,t;

     for(i=head[u];i!=-1;i=edges[i].next)

     {

         v=edges[i].v;

         if(v==pre) continue;

         t=DFS(v,u);

         if(t>m1) m2=m1,m1=t,f[u]=i;

         else if(t>m2) m2=t;

     }

     if(M<m1+m2) MM=u,M=m1+m2;

     dp[u]=m1;

     return dp[u]+1;

 }

 

 

 void DFS1(int u,int pre)

 {

     int i,j,v;

     son[u]=0;

 

     for(i=head[u];i!=-1;i=edges[i].next)

     {

         v=edges[i].v;

         if(v==pre||i==E||i==(E^1)) continue;

         ans[v]=C;

         DFS1(v,u);

         son[u]++;

     }

     if(!son[u])

     {

         hash[u]=1;

         return;

     }

     for(j=0,i=head[u];i!=-1;i=edges[i].next)

     {

         v=edges[i].v;

         if(v==pre||i==E||i==(E^1)) continue;

         q[j].hash=hash[v];

         q[j++].ans=ans[v];

     }

     sort(q,q+son[u],cmp);

     hash[u]=977872;

     for(i=0;i<son[u];i++)

     {

         for(j=i;j<son[u]&&q[i].hash==q[j].hash;j++)

         {

             hash[u]*=P;

             hash[u]^=q[j].hash;

             hash[u]%=mod;

         }

         j--;

         ans[u]*=cal(q[i].ans+j-i,j-i+1);

         ans[u]%=mod;

         i=j;

     }

 }

 

 int main()

 {

     init();

     while(scanf("%d%d",&n,&C)!=-1)

     {

         memset(head,-1,sizeof(head));

         e=2;

         int i,u,v;

         for(i=1;i<n;i++)

         {

             scanf("%d%d",&u,&v);

             Add(u,v);

             Add(v,u);

         }

         M=-1;DFS(1,-1);

 

         if(M&1)

         {

             while(dp[MM]*2>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
",ans[MM]);

     }

     return 0;

 }