这是一个未被验证过正确性的判断有根树同构的哈希函数。可以记忆化搜索或者dfs求得。
f(u)表示以u为根的子树的哈希值。
size(u)表示以u为根的子树的大小。
son(u)表示u的儿子数量。
chi表示u的第i个儿子。
p为种子。
O(n)。
typedef unsigned long long ull;
#define N 100001
const ull seed=127;
ull f[N],seeds[N];
void dfs(int U)
{
size[U]=1;
int t=0;
for(int i=first[U];i;i=next[i])
{
dfs(v[i]);
f[U]+=f[v[i]]*seeds[size[U]-1];
size[U]+=size[v[i]];
}
f[U]+=seeds[size[U]-1]*(son[U]+1);
}
原文：http://www.cnblogs.com/autsky-jadek/p/4539500.html