洛谷-5043 【模板】树同构（[BJOI2015]树的同构）

题目描述
树是一种很常见的数据结构。
我们把N个点，N-1条边的连通无向图称为树。
若将某个点作为根，从根开始遍历，则其它的点都有一个前驱，这个树就成为有根树。
对于两个树$T_1$和$T_2$，如果能够把树$T_1$的所有点重新标号，使得树$T_1$和树$T_2$完全相同，那么这两个树是同构的。也就是说，它们具有相同的形态。
现在，给你M个有根树，请你把它们按同构关系分成若干个等价类。
输入格式
第一行，一个整数M。
接下来M行，每行包含若干个整数，表示一个树。第一个整数N表示点数。接下来N个整数，依次表示编号为1到N的每个点的父亲结点的编号。根节点父亲结点编号为0。
输出格式
输出M行，每行一个整数，表示与每个树同构的树的最小编号。

输入输出样例
输入 #1
4
4 0 1 1 2
4 2 0 2 3
4 0 1 1 1
4 0 1 2 3

输出 #1
1
1
3
1

说明/提示
编号为1, 2, 4 的树是同构的。编号为3 的树只与它自身同构。
100% 的数据中，$1\le N,M\le 50$。

#include<stdio.h>
struct node{
    int ch[2];
    int size;
    int val;
};
node nn[4096];
int num;
void add(char* s,int n,int now){
    nn[now].size++;
    if(n==0){
        nn[now].val++;
        return;
    }
    if(!nn[now].ch[s[0]-'0']){
        num++;
        nn[num].ch[0]=0;
        nn[num].ch[1]=0;
        nn[num].size=0;
        nn[num].val=0;
        nn[now].ch[s[0]-'0']=num;
    }
    add(s+1,n-1,nn[now].ch[s[0]-'0']);
}
int query(char* s,int n,int now,int i){
    if(n==0){
        if(nn[now].val==0) nn[now].val=i;
        return nn[now].val;
    }
    if(!nn[now].ch[s[0]-'0']){
        num++;
        nn[num].ch[0]=0;
        nn[num].ch[1]=0;
        nn[num].size=0;
        nn[num].val=0;
        nn[now].ch[s[0]-'0']=num;
    }
    return query(s+1,n-1,nn[now].ch[s[0]-'0'],i);
}
void sol(char* s,int n){
    if(n==0) return;
    int lastwz=0;
    int cnt=0;
    for(int i=0;i<n;i++){
        if(s[i]=='0') cnt++;
        else cnt--;
        if(cnt==0){
            sol(s+lastwz+1,i-lastwz-1);
            lastwz=i+1;
        }
    }
    num=0;
    nn[num].ch[0]=0;
    nn[num].ch[1]=0;
    nn[num].size=0;
    nn[num].val=0;
    cnt=0;
    lastwz=0;
    for(int i=0;i<n;i++){
        if(s[i]=='0') cnt++;
        else cnt--;
        if(cnt==0){
            add(s+lastwz,i-lastwz+1,0);
            lastwz=i+1;
        }
    }
    int now=0;
    cnt=0;
    while(1){
        if(nn[now].size==0) break;
        nn[now].size--;
        if(nn[now].val){
            nn[now].val--;
            now=0;
            continue;
        }
        if(nn[now].ch[0]&&nn[nn[now].ch[0]].size){
            s[cnt]='0';
            now=nn[now].ch[0];
        }
        else{
            s[cnt]='1';
            now=nn[now].ch[1];
        }
        cnt++;
    }
}
char s[64][128];
int len[64];
int head[64],last[128],to[128],cnt=0;
int size[64];
void add(int u,int v){
    cnt++;
    last[cnt]=head[u];
    head[u]=cnt;
    to[cnt]=v;
}
void dfs(int u,int f){
    size[u]=1;
    for(int i=head[u];i;i=last[i]){
        int v=to[i];
        if(v==f) continue;
        dfs(v,u);
        size[u]+=size[v];
    }
}
int findroot(int u,int f,int n){
    for(int i=head[u];i;i=last[i]){
        int v=to[i];
        if(v==f) continue;
        if(size[v]<=n) continue;
        return findroot(v,u,n);
    }
    return u;
}
int tim;
void dfs2(int u,int f,int id){
    s[id][tim]='0';
    tim++;
    for(int i=head[u];i;i=last[i]){
        int v=to[i];
        if(v==f) continue;
        dfs2(v,u,id);
    }
    s[id][tim]='1';
    tim++;
}
int main(){
    int m;
    scanf("%d",&m);
    for(int i=1;i<=m;i++){
        int n;
        scanf("%d",&n);
        for(int j=1;j<=n;j++) head[j]=0;
        cnt=0;
        for(int j=1;j<=n;j++){
            int v;
            scanf("%d",&v);
            if(v){
                add(j,v);
                add(v,j);
            }
        }
        dfs(1,0);
        int u=findroot(1,0,n>>1);
        int v=0;
        for(int j=head[u];j;j=last[j]){
            if((size[to[j]]<<1)==n){
                v=to[j];
                break;
            }
        }
        tim=0;
        dfs2(u,v,i);
        if(v) dfs2(v,u,i);
        sol(s[i],tim);
        len[i]=tim;
    }
    num=0;
    nn[num].ch[0]=0;
    nn[num].ch[1]=0;
    nn[num].size=0;
    nn[num].val=0;
    for(int i=1;i<=m;i++) printf("%d\n",query(s[i],len[i],0,i));
    return 0;
}