引入

树同构：两棵树如果形态相同，就称这两棵树同构。即存在一个排列 \(p\) ，将其中一棵树的编号 \(i\) 改为 \(p_i\) ，使得这棵树和另外一棵树完全相同。

树哈希可以用来干什么

我们有时需要判断一些树是否同构。这时，我们可以选择一种恰当的哈希方式来将树的结构映射成一个便于储存的哈希值。

实现树哈希

为了下文描述方便，我们先定义一些变量：

\(u\) ：当前节点

\(v\) ：表示以 \(u\) 为父亲的儿子

\(h_i\)​​​​​​​ ：以 \(i\)​​​​​​​ 为根的子树的哈希值。特别地，若 \(i\)​​​​​ 为叶子节点，则 \(h_i=1\)​​​​​​ 。

\(f_i\) ：以 \(i\) 为根时整棵树的哈希值。

\(siz_i\)​​​​ ：以 \(i\)​​​​​ 为根的子树的大小。

\(prime_i\) ：排名第 \(i\) 的质数

常用的一种树哈希的公式：

\[h_u = 1 + \sum h_v \times prime_{siz_v} \]

Tips：在判断树同构的时候还要记得判断一下树的大小。

任意节点作根的树哈希值

公式：

\[f_v = (f_u - h_v \times prime_{siz_v}) \times prime_{n-siz_v} + h_v \]

例题：

P5043 【模板】树同构（[BJOI2015]树的同构）

Description：归类所有结构相同的树。

Solution：树哈希模板题。注意，在判断时要判断两棵树中的每个点作为根的哈希值全部一一匹配时这两棵树同构。我们在判断是否一一匹配时可以再进行一遍哈希（哈希套哈希）。

Code：

#include <map>
#include <cstdio>
#include <vector>
#include <cstring>
#include <algorithm>
typedef long long ll;
using namespace std;
const ll seed=233;
const int N=5e1+7,MAX=4e3+7;

map<ll,int> vis;

vector<int> prime,edge[N];

ll h[N],f[N];
int siz[N];
bool IsPrime[MAX];

int n,m;

inline void GetPrime(int limit) {
	memset(IsPrime,true,sizeof(IsPrime));
	IsPrime[1]=false;
	for(int i=2;i<=limit;++i) {
		if(IsPrime[i])
			prime.push_back(i);
		for(int j=0;j<prime.size() && i*prime[j]<=limit;++j) {
			IsPrime[i*prime[j]]=false;
			if(!(i%prime[j]))
				break;
		}
	}
}

inline void add(int u,int v) {
	edge[u].push_back(v);
	edge[v].push_back(u);
}

inline void Clean() {
	for(int i=1;i<=n;++i) {
		edge[i].clear();
		h[i]=0,f[i]=0,siz[i]=1;
	}
	
}

inline void Hash(int u,int father) {
	for(int i=0,v;i<edge[u].size();++i) {
		v=edge[u][i];
		if(v!=father) {
			Hash(v,u);
			siz[u]+=siz[v];
			h[u]+=h[v]*prime[siz[v]];
		}
	}
	++h[u];
}

inline void GetEachHash(int u,int father) {
	if(father)
		f[u]=(f[father]-h[u]*prime[siz[u]])*prime[n-siz[u]]+h[u];
	for(int i=0,v;i<edge[u].size();++i) {
		v=edge[u][i];
		if(v!=father)
			GetEachHash(v,u);
	}
}

signed main() {
	GetPrime(MAX); // 求质数
	scanf("%d",&m);
	for(int task=1;task<=m;++task) {
		scanf("%d",&n);
		Clean();
		for(int i=1,u;i<=n;++i) {
			scanf("%d",&u);
			if(u)
				add(u,i);
		}
		Hash(1,0); // 求出以 1 为根的各个子树的哈希值
		f[1]=h[1];
		GetEachHash(1,0); // 推广到任意节点作根的树哈希值
		sort(f+1,f+n+1);
		ll res=0;
		for(int i=1;i<=n;++i)
			res=res*seed+f[i]; // 将对每棵树一一匹配的操作用哈希值存起来比较
		if(vis.find(res)==vis.end())
			printf("%d\n",task),vis[res]=task;
		else
			printf("%d\n",vis[res]);
	}
    return 0;
}

P4323 [JSOI2016]独特的树叶

Description：找出多余的叶子节点。

Solution：先求出 \(A\) 中每个点为根的哈希值，再对于 \(B\) 中每个叶子节点的父亲，求出减去该节点相连的一个叶子节点后该子树的哈希值。如果与 \(A\)​​ 中某个节点哈希值相同，说明该节点相连的叶子节点都是可能被去除的，更新答案。

Code：咕咕咕了