اُپدیا

درخت را از دو راس یا تک راس مرکز آن، آویزان کرده و آن را $Hash$ می‌کنیم. دو درخت یک‌ریخت‌اند اگر مقدار hash_value آن دو برابر باشد.
ساختار اصلی کد ارائه شده همان الگوریتم پیدا کردن مرکز درخت است که در میان آن همواره hash_value زیردرخت هر راس نیز محاسبه شده است.

const int Maxn = 1e5 + 3, M = 1e9 + 9;
const long long Z = 239;
int n, deg[Maxn], hash_value[Maxn], h[Maxn];
vector < int > adj[Maxn];

int getHash () {
	int center[2] = {0, 0};
	queue < int > q;
	for(int i = 1; i <= n; ++i)
		if (deg[i] == 1) {
			q.push(i);
			h[i] = 1;
		}
	while(!q.empty()) {
		int v = q.front();
		q.pop();

		int par = 0;
		vector < int > hash_child;
		for(int u: adj[v]) {
			if (h[u] && h[u] < h[v])
				hash_child.push_back(hash_value[u]);
			else if (--deg[u] == 1) {
				q.push(u);
				h[u] = h[v] + 1;
			}
			if (h[u] > h[v])
				par = u;
		}
		if (!par) {
			center[1] = center[0];
			center[0] = v;
		}
		sort(hash_child.begin(), hash_child.end() );
		hash_value[v] = ( (adj[v].size() * Z % M) * h[v]) % M;
		for(int h: hash_child)
			hash_value[v] = (hash_value[v] * Z + h) % M;
	}

	if (hash_value[center[1]] > hash_value[center[0]])
		swap (center[0], center[1]);
	return (hash_value[center[1]] * Z + hash_value[center[0]]) % M;
}