用来判断两棵有根树是否同构，很简单，稍微记录一下细节(贴个代码)

我会告诉你这篇博客其实是用来测试一下自己瞎折腾的新主题的吗

Brief Introduction

大致Hash的思路与普通字符串Hash类似，需要注意的点：

  • 树Hash需要两个不同的Base和一个Rest来进行Hash（具体见代码），即先对子树用Base1Hash起来后，对这个Hash值用Base2和Rest进行Hash
  • 求出儿子的Hash值后需要将它们排序再计算
  • 具体Hash策略可以模意义下普通Hash，也可以直接异或
  • 此外，如果需要判断无根树是否同构的话，可以把重心作为根进行Hash

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
const int Base1 = 20030123, Base2 = 20030618, Rest = 19260817;

ULL Hash[Maxm];

inline void get_hash (int x)
{
	ULL Save[Maxm];
	Save[0] = 0;

	int cnt = 0;
	for (int y : G[x]) 
	{
		if (y == fa[x]) continue;
		fa[y] = x;
		get_hash (y);
		Save[++cnt] = Hash[y];
	}

	sort(Save + 1, Save + cnt + 1);
	Hash[x] = 0;
	for (int i = 1; i <= cnt; ++i)
		Hash[x] = Hash[x] * Base1 + Save[i];

	Hash[x] = Hash[x] * Base2 + Rest;
}