題意：給定n（n<=50000）個點組成的樹，用m（m<=100000）種顏色染色，問不重復（通過旋轉）的染色方法數有多少種。
題解：這題完全是看人家的代碼看懂的唉…
首先找到樹的中心（不是重心），中心的定義是樹的直徑的中點，如果直徑上節點個數是偶數，那麼在中間建立一個新的節點。
然後從中心dfs，對於每一棵子樹得到相應的hash值（hash方法：hash[i]= A * (hash[j1]*B)^hash[j2]*B.....^hash[jn]*C%D;（順序執行）），
排序之後同構的子樹一定是排列在相鄰的位置，這樣通過隔板法解x1+x2+……+xans[i] = cnt得到染當前形狀子樹的方法數，然後得到最後的答案。
下面簡單說說取中點dfs的正確性：
定義性質x：以u節點為根節點fa為u的father節點時，任意hash[son]都不等於hash[fa]（上方子樹的hash值）。
如果取中點dfs那麼對於dfs到的所有節點上面的性質都滿足，定義longest[i]為以i為根節點到葉子節點的最大距離，l為樹的直徑。
因為longest[fa]（上方子樹 && fa ！= 中心）>=l/2，longest[i]< l/2，所以滿足性質x，這樣就能保證正確性，不會把同構的子樹遺漏掉。
Sure原創，轉載請注明出處。
[cpp]
#include <iostream>
#include <cstdio>
#include <memory.h>
#include <algorithm>
using namespace std;
const int maxn = 50005;
const int maxm = 100002;
const int leaf = 9778972;
const int yin = 10003;
const int yy = 131237;
const int mod = 1000000007;
struct node
{
int v;
int next;
}edge[maxn << 1];
struct H
{
__int64 hash,ans;
bool operator < (const H &other) const
{
return hash < other.hash;
}
}val[maxn];
int head[maxn],down[maxn],longest[maxn];
__int64 ans[maxn],hash[maxn],A[maxm];
int m,n,bj,idx,root,path;
void prepare()
{
A[0] = A[1] = 1;
for(int i=2;i<maxm;i++)
{
A[i] = A[i-1] * i;
A[i] %= mod;
}
return;
}
void init()
{
memset(head,-1,sizeof(head));
memset(down,-1,sizeof(down));
idx = path = 0;
bj = root = -1;
return;
}
void addedge(int u,int v)
{
edge[idx].v = v;
edge[idx].next = head[u];
head[u] = idx++;
edge[idx].v = u;
edge[idx].next = head[v];
head[v] = idx++;
return;
}
void read()
{
int u,v;
for(int i=1;i<n;i++)
{
scanf("%d %d",&u,&v);
addedge(u,v);
}
return;
}
__int64 powmi(__int64 a,int x)
{
__int64 res = 1;
while(x)
{
if(x & 1)
{
res *= a;
res %= mod;
}
a *= a;
a %= mod;
x >>= 1;
}
return res;
}
__int64 C(__int64 n,int m)
{
if(n == 1LL * m) return 1LL;
__int64 res = 1;
for(int i=1;i<=m;i++)
{
res *= 1LL * (n - i + 1);
res %= mod;
}
res *= powmi(A[m] , mod-2);
return res % mod;
}
void DFS(int st,int pre)
{
int l = 0,ll = 0;
for(int i=head[st];i != -1;i=edge[i].next)
{
if(edge[i].v == pre) continue;
DFS(edge[i].v , st);
if(longest[edge[i].v] > l)
{
ll = l;
l = longest[edge[i].v];
down[st] = i;
}
else if(longest[edge[i].v] > ll) ll = longest[edge[i].v];
}
if(l + ll + 1 > path)
{
path = l + ll + 1;
root = st;
}
longest[st] = l + 1;
return;
}
void make()
{
DFS(1,0);
if(path & 1)
{
while(longest[root] * 2 - 1 > path)
{
root = edge[down[root]].v;
}
ans[root] = 1LL * m;
}
else
{
while(longest[root] * 2 - 2 > path)
{
root = edge[down[root]].v;
}
addedge(root , ++n);
addedge(n , edge[down[root]].v);
bj = down[root];
root = n;
ans[root] = 1LL;
}
return;
}
void dfs(int st,int pre)
{
int num = 0;
for(int i=head[st];i != -1;i=edge[i].next)
{
if(edge[i].v == pre) continue;
if(bj != -1 && (i == bj || i == (bj ^ 1))) continue;
num++;
ans[edge[i].v] = 1LL * m;
dfs(edge[i].v , st);
}
if(num == 0)
{
hash[st] = leaf;
return;
}
int c = 0;
for(int i=head[st];i != -1;i=edge[i].next)
{
if(edge[i].v == pre) continue;
if(bj != -1 && (i == bj || i == (bj ^ 1))) continue;
val[c].hash = hash[edge[i].v];
val[c++].ans = ans[edge[i].v];
}
sort(val , val + num);
hash[st] = leaf;
for(int i=0;i<num;)
{
int j = i;
for(;j<num && val[i].hash == val[j].hash;j++)
{
hash[st] *= yin;
hash[st] ^= val[j].hash;
hash[st] %= mod;
}
hash[st] = hash[st] * yy % mod;
ans[st] *= C(val[i].ans + j - i - 1, j - i);
ans[st] %= mod;
i = j;
}
return;
}
int main()
{
prepare();
while(~scanf("%d %d",&n,&m))
{
init();
read();
make();
dfs(root , 0);
printf("%I64d\n",ans[root]);
}
return 0;
}
