嗯哼哼WA on#2 #4一直输出1(个)1(个)1(个)啊啊啊啊啊啊 Maxn开105就过了。
#include<bits/stdc++.h>
#define Maxn 105
using namespace std;
int size[Maxn],N,M,head[Maxn],hash[Maxn],ans[Maxn],prime[Maxn],p[Maxn],tot=0,cnt=0;
bool is_prime[Maxn];
struct edge{int next,to;}e[Maxn<<1];
inline void add(int x,int y)
{
e[++cnt].next=head[x];
e[cnt].to=y;
head[x]=cnt;
}
inline void get_size(int now,int fa)
{
size[now]=1;
for (int i=head[now];i;i=e[i].next)
{
int v=e[i].to;
if (v==fa) continue;
get_size(v,now);
size[now]+=size[v];
}
}
inline void get_hash(int now,int fa)
{
hash[now]=size[now]*prime[size[now]]%19260817;
for (int i=head[now];i;i=e[i].next)
{
int v=e[i].to;
if (v==fa) continue;
get_hash(v,now);
hash[now]+=hash[v];
hash[now]%=19260817;
}
}
int main()
{
for (int i=2;i<=Maxn-5;i++)
{
if (!is_prime[i]) prime[++tot]=i;
for (int j=1;j<=tot&&i*prime[j]<=Maxn-5;j++)
{
is_prime[i*prime[j]]=1;
if (i%prime[j]==0) break;
}
}
scanf("%d",&M);
for (int i=1;i<=M;i++)
{
memset(head,0,sizeof(head));
memset(e,0,sizeof(e));
cnt=0;
scanf("%d",&N);
for (int x,j=1;j<=N;j++)
{
scanf("%d",&x);
if (x==0) continue;
add(x,j),add(j,x);
}
for (int rt=1;rt<=N;rt++)
{
memset(size,0,sizeof(size));
memset(hash,0,sizeof(hash));
get_size(rt,0);
get_hash(rt,0);
p[rt]=hash[rt];
}
sort(p+1,p+N+1);
for (int j=1;j<=N;j++) ans[i]+=p[j]*prime[j]%19260817,ans[i]%=19260817;
}
for (int i=1;i<=M;i++)
for (int j=1;j<=i;j++)
if (ans[i]==ans[j]) {cout<<j<<endl;break;}
return 0;
}