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

const ull mask = 1145141919810;
//mask取随机数即可
inline ull g(ull x) {
	x ^= mask;
	x ^= x << 13;
	x ^= x >> 7;
	x ^= x << 17;
	x ^= mask;
  // g函数通常写法
	return x;
}
void dfs(int s, int fa) {
	Hash[s] = 1ull;//c取1
	for(int to: e[s]) {
		if(to == fa) continue;
		dfs(to, s);
		Hash[s] += g(Hash[to]);
	}
}

#include <bits/stdc++.h>
#define rep(i, a, b) for(register int i = a; i <= b; ++i)
typedef unsigned long long ull;
using namespace std;
constexpr int N = 55;
const ull mask = mt19937_64(time(0))();
inline ull g(ull x) {
	x ^= mask;
	x ^= x << 13;
	x ^= x >> 7;
	x ^= x << 17;
	x ^= mask;
	return x;
}
long long target, g1, g2, m, n, root, p, dp[N], dep[N], siz[N];
vector<int> e[N];
void init(int s, int fa) {
	dep[s] = dep[fa] + 1;
	dp[root] += dep[s];
	siz[s] = 1;
	for(register int to : e[s]) {
		if(to == fa) continue;
		init(to, s);
		siz[s] += siz[to];
	}
}
void dfs(int s, int fa) {
	for(register int to : e[s]) {
		if(to == fa) continue;
		dp[to] = dp[s] + n - siz[to] * 2;
		dfs(to, s);
	}
}
ull Hash(int s, int fa) {
	ull hash = 1ull;
	for(register int to : e[s]) {
		if(to == fa) continue;
		hash += g(Hash(to, s));
	}
	return hash;
}
map<pair<ull, ull>, int>mp;
int main() {
	ios :: sync_with_stdio(0), cin.tie(0), cout.tie(0);
	cin >> m;
	rep(i, 1, m) {
		cin >> n;
		g1 = g2 = 0;
		memset(dp, 0, sizeof dp);
		memset(dep, 0, sizeof dep);
		memset(siz, 0, sizeof siz);
		target = 1e18;
		rep(j, 1, 50) e[j].clear();
		rep(j, 1, n) {
			cin >> p;
			if(!p) {
				root = j;
				continue;
			}
			e[p].push_back(j);
			e[j].push_back(p);
		}
		init(root, 0);
		dfs(root, 0);
		rep(j, 1, n) {
			target = min(target, dp[j]);
		}
		rep(j, 1, n) {
			if(dp[j] == target) {
				if(g1) {
					g2 = j;
				}
				else {
					g1 = j;
				}
			}
		}
      //预处理出树的重心
		ull p1 = Hash(g1, 0);
		ull p2 = Hash(g2, 0);
		if(p1 > p2) {
			swap(p1, p2);
		}
		auto now = make_pair(p1, p2);
    //记录哈希值，存储进map即可
		if(mp[now]) {
			cout << mp[now] << '\n';
		}
		else {
			cout << i << '\n';
			mp[now] = i;
		}
	}
	return 0;
}