introduce

Tree Isomorphism: if two trees have the same shape, they are called isomorphic. That is, there is an arrangement \ (P \), change the number of one tree \ (I \) to \ (p_i \), so that this tree is exactly the same as the other tree.

What can tree hashes be used for

Sometimes we need to judge whether some trees are isomorphic. At this time, we can choose an appropriate hash method to map the tree structure into a hash value that is easy to store.

Implement tree hash

For the convenience of the following description, we first define some variables:

\(u \): current node

\(v \): refers to the son whose father is \ (u \)

\(h_i \): the hash value of the subtree with \ (I \) as the root. In particular, if \ (I \) is a leaf node, then \ (h_i=1 \).

\(f_i \): the hash value of the whole tree when taking \ (I \) as the root.

\(siz_i \): the size of the subtree with \ (I \) as the root.

\(prime_i \): the prime number ranking \ (I \)

A commonly used tree hash formula:

Tips: remember to judge the size of the tree when judging the isomorphism of the tree.

Hash value of tree with any node as root

Formula:

Example:

P5043 [template] tree isomorphism ([BJOI2015] tree isomorphism)

Description: classify all trees with the same structure.

Solution: tree hash template question. Note that when judging, it is necessary to judge that the hash values of each point as the root of the two trees match one by one, and the two trees are isomorphic. We can hash again (hash set hash) when judging whether it matches one by one.

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); // Find prime number
	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); // Find the hash value of each subtree with 1 as the root
		f[1]=h[1];
		GetEachHash(1,0); // It is extended to the tree hash value with any node as the root
		sort(f+1,f+n+1);
		ll res=0;
		for(int i=1;i<=n;++i)
			res=res*seed+f[i]; // The operation of matching each tree one by one is saved and compared with the hash value
		if(vis.find(res)==vis.end())
			printf("%d\n",task),vis[res]=task;
		else
			printf("%d\n",vis[res]);
	}
    return 0;
}

P4323 [JSOI2016] unique leaves

Description: find out the redundant leaf nodes.

Solution: first find the hash value of each point in \ (A \) as the root, and then for the father of each leaf node in \ (B \), find the hash value of the subtree after subtracting A leaf node connected to the node. If the hash value of A node in \ (A \) is the same, it means that the leaf nodes connected to the node may be removed. Update the answer.

Code: Goo Goo