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);
补充：软件开发 , C++ ,
