我们有时需要判断一些树是否同构。这时，选择恰当的Hash方式来将树映射成一个便于储存的Hash值（一般是 32 位或 64 位整数）是一个优秀的方案。
树Hash定义在有根树上。判断无根树同构的时候，可以比较重心为根的Hash值或者比较每个点为根的Hash值。
树哈希有很多种哈希方式，下面介绍其中一种：
$f_x$表示$x$为根的子树的Hash值，$son_x$表示$x$的儿子结点集合，$size_y$表示$y$为根的子树规模，$prime(i)$表示第$i$个素数，则
$$
f_x = 1 + sum_{yin son_x}{f_y imes prime(size_y)}
$$
注意到我们求得的是子树的Hash值，也就是说只有当根一样时同构的两棵子树 hash 值才相同。如果数据范围较小，我们可以暴力求出以每个点为根时的Hash值，也可以通过up and down树形dp的方式，遍历树两遍求出以每个点为根时的Hash值，排序后比较。
如果数据范围较大，我们可以通过找重心的方式来优化复杂度。（一棵树的重心最多只有两个，分别比较即可）
例题1：洛谷P5043 [模板]树同构
判断无根树同构，通过两遍dfs树形dp，求出每个点为根时的Hash值，排序后比较即可。
#include <cstdio> #include <cstring> #include <vector> #include <algorithm> using std::vector; using std::sort; const int N = 60; int f[N], g[N], siz[N]; int n; struct Edge { int nex, to; } edge[N<<1]; int head[N], tot; vector<int> hs[N]; bool isprime[1000]; int prime[N]; void init(int i) { tot = 1; memset(head, 0, sizeof(head)); hs[i].clear(); } void add_edge(int u, int v) { edge[tot].to = v; edge[tot].nex = head[u]; head[u] = tot++; } void get_prime(int MAX) { int x = 0; memset(isprime, true, sizeof(isprime)); for (int i = 2; i < MAX; i++) { if (x > 55) break; if (isprime[i]) prime[x++] = i; for (int j = 0; j < x; j++) { if (i * prime[j] >= MAX) break; isprime[i * prime[j]] = 0; if (i % prime[j] == 0) break; } } } void dfs1(int x, int fa) { siz[x] = f[x] = 1; for (int i = head[x]; i; i = edge[i].nex) { int y = edge[i].to; if (y == fa) continue; dfs1(y, x); f[x] += f[y] * prime[siz[y]]; siz[x] += siz[y]; } } void dfs2(int x, int fa, int fa_f) { g[x] = f[x] + fa_f * prime[n-siz[x]]; fa_f *= prime[n-siz[x]]; for (int i = head[x]; i; i = edge[i].nex) { int y = edge[i].to; if (y == fa) continue; dfs2(y, x, fa_f + f[x] - f[y] * prime[siz[y]]); } } bool Equal(int x, int y) { if (hs[x].size() != hs[y].size()) return false; for (int i = 0; i < hs[x].size(); i++) { if (hs[x][i] != hs[y][i]) return false; } return true; } int main() { get_prime(1000); int m; while (~scanf("%d", &m)) { for (int i = 1; i <= m; i++) { init(i); scanf("%d", &n); for (int j = 1, x; j <= n; j++) { scanf("%d", &x); if (x) add_edge(x, j), add_edge(j, x); } dfs1(1, 0); dfs2(1, 0, 0); for (int j = 1; j <= n; j++) hs[i].push_back(g[j]); sort(hs[i].begin(), hs[i].end()); } puts("1"); for (int i = 2; i <= m; i++) { for (int j = 1; j <= i; j++) { if (Equal(i, j)) { printf("%d ", j); break; } } } } return 0; }
贴一个树重心为根求Hash值进行比较的代码，用了其他Hash方法：
inline void DFS(re int x,re int fa){ size[x]=1; re int i,y,res=0; for(i=h[x];i;i=e[i].next){ y=e[i].to;if(y==fa)continue; DFS(y,x); size[x]+=size[y]; res=max(res,size[y]); } res=max(res,n-size[x]);d[x]=res; maxl=min(maxl,res); } inline int Solve(re int x,re int fa){ re int i,y,res=2333; re vector<int > t; for(i=h[x];i;i=e[i].next){ y=e[i].to;if(y==fa)continue; t.push_back(Solve(y,x)); } sort(t.begin(),t.end()); for(i=0;i<t.size();++i)res=((res*Mul)^t[i])%Mod; return res; } int main(void){ re int i,j,x; scanf("%d",&m); memset(ans,INF,sizeof ans); for(i=1;i<=m;++i){ scanf("%d",&n); cnt=0;memset(h,0,sizeof h);tot=0; for(j=1;j<=n;++j){scanf("%d",&x);if(x){AddEdge(j,x);AddEdge(x,j);}} maxl=INF;DFS(1,0); for(j=1;j<=n;++j){if(d[j]==maxl)rt[++tot]=j;} for(j=1;j<=tot;++j)ans[i]=min(ans[i],Solve(rt[j],0)); for(j=1;j<=i;++j)if(ans[j]==ans[i]){printf("%d ",j);break;} } return 0; }
处理出树A每个点为根时的Hash值，放进set里；
处理出树B每个点为根时的Hash值，对于叶子结点，计算其父亲结点为根，去掉此叶子结点后的Hash值（也就是减去第一个素数2），在set中查找是否存在此值，是则说明此叶子结点为多余的叶子。
#include <cstdio> #include <cstring> #include <unordered_set> using std::unordered_set; const int N = 100010; bool isprime[2000010]; int prime[N]; int in[N], near[N]; struct Edge { int nex, to; }; struct Tree { int f[N], g[N], siz[N], head[N]; int n, tot; Edge edge[N<<1]; void init(int nn) { n = nn; tot = 1; memset(head, 0, sizeof(head)); } void add_edge(int u, int v) { edge[tot].to = v; edge[tot].nex = head[u]; head[u] = tot++; } void dfs1(int x, int fa) { siz[x] = f[x] = 1; for (int i = head[x]; i; i = edge[i].nex) { int y = edge[i].to; if (y == fa) continue; dfs1(y, x); f[x] += f[y] * prime[siz[y]]; siz[x] += siz[y]; } } void dfs2(int x, int fa, int fa_f) { g[x] = f[x] + fa_f * prime[n-siz[x]]; fa_f *= prime[n-siz[x]]; for (int i = head[x]; i; i = edge[i].nex) { int y = edge[i].to; if (y == fa) continue; dfs2(y, x, fa_f + f[x] - f[y] * prime[siz[y]]); } } } tree1, tree2; void get_prime(int MAX) { int x = 1; memset(isprime, true, sizeof(isprime)); for (int i = 2; i < MAX; i++) { if (x > N - 5) break; if (isprime[i]) prime[x++] = i; for (int j = 1; j < x; j++) { if (i * prime[j] >= MAX) break; isprime[i * prime[j]] = 0; if (i % prime[j] == 0) break; } } } int main() { get_prime(2000010); int n; while (~scanf("%d", &n)) { tree1.init(n); tree2.init(n + 1); memset(in, 0, sizeof(in)); unordered_set<int> se; for (int i = 0, u, v; i < n - 1; i++) { scanf("%d %d", &u, &v); tree1.add_edge(u, v); tree1.add_edge(v, u); } for (int i = 0, u, v; i < n; i++) { scanf("%d %d", &u, &v); tree2.add_edge(u, v); tree2.add_edge(v, u); ++in[u], ++in[v]; near[u] = v, near[v] = u; } tree1.dfs1(1, 0); tree1.dfs2(1, 0, 0); for (int i = 1; i <= n; i++) se.insert(tree1.g[i]); tree2.dfs1(1, 0); tree2.dfs2(1, 0, 0); for (int i = 1; i <= n + 1; i++) { if (in[i] != 1) continue; if (se.count(tree2.g[near[i]] - 2)) { printf("%d ", i); break; } } } return 0; }