80pts求调
查看原帖
80pts求调
995699
yuxuzhehuan楼主2024/7/31 10:17
#include<bits/stdc++.h>
using namespace std;
const int _=1e+2,mod=1019260817,a=19491001;
int m,n[_],u,size[_],ans,G[3],Gl,de[_],hash1[_],p[_]={1},cl;
struct node
{   int a,b;
	bool operator <(const node &o)const
	{	if(o.a==a)	return b<o.b;
		return a<o.a;
	}
	bool operator ==(const node &o)const
	{	return a==o.a&&b==o.b;
	}
}	c[_],f[_];
vector<int>tr[_];
inline int read()
{	int x=0,f=1;char ch=getchar();
	for(;ch<'0'||'9'<ch;ch=getchar())	if(ch=='-')	f=-1;
	for(;'0'<=ch&&ch<='9';ch=getchar())	x=(x<<1)+(x<<3)+ch-'0';
	return x*f;
}
void dfsg(int u,int fa,int t)
{	size[u]=1;int tmp=0;
    for(auto v:tr[u])   if(v!=fa)
    {   dfsg(v,u,t);
        size[u]+=size[v],tmp=max(tmp,size[v]);
	}
	tmp=max(tmp,n[t]-size[u]);
	if(tmp<=ans)
	{   if(tmp<ans) Gl=0;
	    G[++Gl]=u,ans=tmp;
	}
}
void dfs(int u,int fa,int t)
{   hash1[u]=1ll*de[u]*p[1]%mod,size[u]=1;
    for(auto v:tr[u])   if(v!=fa)	de[v]=de[u]+1,dfs(v,u,t);
    cl=0;
    for(auto v:tr[u])	if(v!=fa)	c[++cl].a=hash1[v],c[cl].b=size[v];
    sort(c+1,c+cl+1);
    for(int i=1;i<=cl;i++)	hash1[u]+=1ll*c[i].a*p[size[u]]%mod,hash1[u]%=mod,size[u]+=c[i].b;
}
signed main()
{	m=read();
	for(int i=1;i<=50;i++)  p[i]=1ll*p[i-1]*a%mod;
	for(int i=1;i<=m;i++)
	{	n[i]=read(),ans=1<<30,Gl=0;
		memset(hash1,0,sizeof hash1);
		for(int j=1;j<=n[i];j++)	tr[j].clear();
		for(int j=1;j<=n[i];j++)
		{	u=read();
			if(u)	tr[u].push_back(j),tr[j].push_back(u);
		}
		dfsg(1,0,i),f[i].a=f[i].b=0;
		de[G[1]]=1,dfs(G[1],0,i),f[i].a=hash1[G[1]];
		if(Gl==2)   de[G[2]]=1,dfs(G[2],0,i),f[i].b=hash1[G[2]];
		if(f[i].a<f[i].b)   swap(f[i].a,f[i].b);
	}
	for(int i=1;i<=m;i++)	for(int j=1;j<=i;j++)	if(f[i]==f[j])
	{	printf("%d\n",j);
		break;
	}
	return 0;
}
2024/7/31 10:17
加载中...