Description：

给 $M$ 个树，把它们按同构关系分成若干个等价类，输出等价类最小的编号。

$1\leqslant n\leqslant 50$

Solution：

树哈希，就是枚举每个点作为根，然后 $dfs$ 整棵树，把所有子树的 $hash$ 值拿出来排序，然后作为字符串 $hash$ 起来作为这个点的 $hash$ 值，最后再把所有点为根的值排序 $hash$ 就是这棵树的 $hash$ 值了。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<map>

#include<cctype>

#include<cstring>

using namespace std;

int t;

#define MAXN 52

int n[MAXN];

struct edge

{

	int to,nxt;

}e[MAXN << 1];

int edgenum = 0;

int lin[MAXN] = {0};

void add(int a,int b)

{

	e[++edgenum] = (edge){b,lin[a]};lin[a] = edgenum;

	e[++edgenum] = (edge){a,lin[b]};lin[b] = edgenum;

	return;

}

unsigned int h[MAXN][MAXN];

map<unsigned int,int> p;

unsigned int dfs(int k,int fa)

{

	unsigned int t[MAXN];t[0] = 0;

	unsigned int val = 1;

	for(int i = lin[k];i != 0;i = e[i].nxt)

	{

		if(e[i].to == fa)continue;

		t[++t[0]] = dfs(e[i].to,k);

	}

	sort(t + 1,t + 1 + t[0]);

	for(int i = 1;i <= t[0];++i)val = val * 19260817 + t[i];

	return val;

}

int main()

{

	scanf("%d",&t);

	for(int k = 1;k <= t;++k)

	{

		scanf("%d",&n[k]);

		int fa;

		memset(lin,0,sizeof(lin));

		edgenum = 0;

		for(int i = 1;i <= n[k];++i)

		{

			scanf("%d",&fa);

			if(fa != 0)add(i,fa);

		}

		for(int i = 1;i <= n[k];++i)h[k][i] = dfs(i,0);

		sort(h[k] + 1,h[k] + 1 + n[k]);

		unsigned int hash = 0;

		for(int i = 1;i <= n[k];++i)hash = hash * 19260817 + h[k][i];

		if(p.find(hash) != p.end())printf("%d\n",p[hash]);

		else p[hash] = k,printf("%d\n",k);

	}

	return 0;

}