BZOJ4337 : BJOI2015 树的同构

#include<cstdio>
#include<string>
#include<algorithm>
#define N 55
using namespace std;
int T,n,i,j,k,x,g[N],v[N<<1],nxt[N<<1],ed,f[N],son[N],mx;string h[N],q[N],val[N];
inline void add(int x,int y){v[++ed]=y;nxt[ed]=g[x];g[x]=ed;}
void findroot(int x,int y){
  son[x]=1;f[x]=0;
  for(int i=g[x];i;i=nxt[i])if(v[i]!=y){
    findroot(v[i],x);
    son[x]+=son[v[i]];
    if(son[v[i]]>f[x])f[x]=son[v[i]];
  }
  if(n-son[x]>f[x])f[x]=n-son[x];
  if(f[x]>mx)mx=f[x];
}
void dfs(int x,int y){
  h[x]="(";
  for(int i=g[x];i;i=nxt[i])if(v[i]!=y)dfs(v[i],x);
  int t=0;
  for(int i=g[x];i;i=nxt[i])if(v[i]!=y)q[t++]=h[v[i]];
  if(t>1)std::sort(q,q+t);
  for(int i=0;i<t;i++)h[x]+=q[i];
  h[x]+=")";
}
string solve(){
  int i;string t="";
  scanf("%d",&n);
  for(ed=mx=0,i=1;i<=n;i++)g[i]=0;
  for(i=1;i<=n;i++){
    scanf("%d",&x);
    if(x)add(i,x),add(x,i);
  }
  findroot(1,0);
  for(i=1;i<=n;i++)if(f[i]==mx){
    dfs(i,0);
    if(h[i]>t)t=h[i];
  }
  return t;
}
int main(){
  scanf("%d",&T);
  for(i=1;i<=T;i++)val[i]=solve();
  for(i=1;i<=T;printf("%d\n",k),i++)for(j=k=i;j;j--)if(val[j]==val[i])k=j;
  return 0;
}