HDU 4275 Color the Tree 树的不重复染色 求树的中心+hash
题意：给定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;
}
