树哈希

作者：XiaoQuQu，发表于 Tue Jul 09 2024。

如果要判两个有根树同构，可以使用树哈希。一个树哈希是 $f_x=(\sum g(f_u))+c\bmod m$，其中 $g$ 是一个从整数到整数的映射，$c$ 是一个常数，$m$ 是模数，可以使用自然溢出。

在这里 $g$ 使用 xor-shift 算法，听 oi-wiki 说要在前后异或一个相同的 mask，不知道有什么用。

const int MAXN = 1e6 + 5;
using ull = unsigned long long;
int n;
ull msk, f[MAXN];
set<ull> st;
vector<int> G[MAXN];

ull nxt(ull x) {
	x ^= msk;
	x ^= x << 13;
	x ^= x >> 5;
	x ^= x << 17;
	x ^= msk;
	return x;
}

void dfs(int x, int fa) {
	f[x] = 19260813;
	for (auto u:G[x]) {
		if (u == fa) continue;
		dfs(u, x);
		f[x] = f[x] + nxt(f[u]);
	}
	st.insert(f[x]);
}

void work() {
	msk = rand();
	cin >> n;
	for (int i = 1, u, v; i < n; ++i) {
		cin >> u >> v;
		G[u].push_back(v);
		G[v].push_back(u);
	}
	dfs(1, 0);
	cout << st.size() << endl;
}

LG5043 树的同构

对于每个树，以这个树里的每个点为根，算一次树哈希，然后暴力判断即可，时间复杂度 $O(n^4)$。

const int MAXN = 55;
using ull = unsigned long long;

int m, n[MAXN];
ull f[MAXN][MAXN][MAXN], msk;
vector<int> G[MAXN][MAXN];

ull nxt(ull x) {
	x ^= msk;
	x ^= x << 13;
	x ^= x >> 5;
	x ^= x << 17;
	x ^= msk;
	return x;
}

void dfs(int x, int fa, int rt, int id) {
	f[id][rt][x] = 19260813;
	for (auto u:G[id][x]) {
		if (u == fa) continue;
		dfs(u, x, rt, id);
		f[id][rt][x] += nxt(f[id][rt][u]);
	}
}

void work() {
	msk = rand();
	cin >> m;
	for (int i = 1; i <= m; ++i) {
		cin >> n[i];
		for (int j = 1; j <= n[i]; ++j) {
			int f; cin >> f;
			if (!f) continue;
			G[i][j].push_back(f);
			G[i][f].push_back(j);
		}
	}
	for (int i = 1; i <= m; ++i) {
		int ans = INT_MAX;
		for (int j = 1; j <= n[i]; ++j) {
			dfs(j, 0, j, i);
			for (int k = 1; k <= i; ++k) {
				if (n[i] != n[k]) continue;
				for (int l = 1; l <= n[k]; ++l) {
					if (f[i][j][j] == f[k][l][l]) ans = min(ans, k);
				}
			}
		}
		cout << ans << endl;
	}
}