[文章目录]
Description
我们把N个点，N-1条边的连通无向图称为树。
若将某个点作为根，从根开始遍历，则其它的点都有一个前驱，这个树就成为有根树。
对于两个树T1和T2，如果能够把树T1的所有点重新标号，使得树T1和树T2完全相同，那么这两个树是同构的。也就是说，它们具有相同的形态。
现在，给你M个有根树，请你把它们按同构关系分成若干个等价类。
hash
求树的重心，如果有两个那么新建一个节点连向他们。
之后只要hash的方法交换儿子不改变树的hash值，愿意怎么hash怎么hash
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef unsigned long long ll;
#define N 100
int rt1,rt2,n,m,head[N],to[N<<1],nxt[N<<1],cnt,siz[N];
ll ha[N];
inline void add(int x,int y)
{
to[++cnt]=y; nxt[cnt]=head[x]; head[x]=cnt;
}
void dfs(int x,int pre)
{
siz[x]=1; int tmp=0;
for(int i=head[x];i;i=nxt[i]) if(to[i]!=pre)
{
dfs(to[i],x); tmp=max(tmp,siz[to[i]]);
siz[x]+=siz[to[i]];
}
tmp=max(tmp,n-siz[x]);
if(tmp<=n/2)
{
if(!rt1) rt1=x;
else rt2=x;
}
}
ll hash(int x,int pre)
{
ll re1=0,re2=1,re3=233;
for(int i=head[x];i;i=nxt[i]) if(to[i]!=pre)
{
ll t=hash(to[i],x);
re1^=t; re2*=t; re3+=t;
}
return ((re1*re2)<<15)^re3;
}
int main()
{
scanf("%d",&m);
for(int i=1;i<=m;++i)
{
memset(head,0,sizeof(int)*(n+10)); cnt=0;
scanf("%d",&n); int x; rt1=rt2=0;
for(int j=1;j<=n;++j)
{
scanf("%d",&x);
if(x) add(x,j),add(j,x);
}
dfs(1,0);
if(rt1) add(0,rt1);
if(rt2) add(0,rt2);
ha[i]=hash(0,0);
}
for(int i=1;i<=m;++i)
for(int j=1;j<=m;++j) if(ha[j]==ha[i])
{
printf("%d\n",j);
break;
}
return 0;
}