Description

树是一种很常见的数据结构。
我们把N个点，N-1条边的连通无向图称为树。
若将某个点作为根，从根开始遍历，则其它的点都有一个前驱，这个树就成为有根树。
对于两个树T1和T2，如果能够把树T1的所有点重新标号，使得树T1和树T2完全相
同，那么这两个树是同构的。也就是说，它们具有相同的形态。
现在，给你M个有根树，请你把它们按同构关系分成若干个等价类。
对于100%的数据，$1\leq N ,M \leq 50$。

Solution

乍一看这数据这么小，直接乱$Hash$就好了。
我的$Hash$是$dfs$每个子节点的$val$排序一遍然后$\times {base}^i$。

Code

#include<bits/stdc++.h>
using namespace std;

#define re register 
#define mod 19260817
#define int long long 

class Quick_Input_Output{
    private:
        static const int S=1<<21;
        #define tc() (A==B&&(B=(A=Rd)+fread(Rd,1,S,stdin),A==B)?EOF:*A++)
        char Rd[S],*A,*B;
        #define pc putchar
    public:
        #undef gc
        #define gc getchar 
        inline int read(){
            int res=0,f=1;char ch=gc();
            while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=gc();}
            while(ch>='0'&&ch<='9') res=res*10+ch-'0',ch=gc();
            return res*f;
        }
        inline void write(int x){
            if(x<0) pc('-'),x=-x;
            if(x<10) pc(x+'0');
            else write(x/10),pc(x%10+'0');
        }
        #undef gc
        #undef pc
}I;

class Solve{
    private:
        int m,n,fir[55],nxt[55*2],son[55*2],tot,ans[55][55],put[55];
    public:
        inline void add(int x,int y){
            ++tot;
            nxt[tot]=fir[x];
            fir[x]=tot;
            son[tot]=y;
        }
        inline int DFS(int x,int fa){
            int sum=1;
            vector<int> v;v.clear();
            for(int to,i=fir[x];i;i=nxt[i]){
                to=son[i];
                if(to==fa) continue ;
                int tmp=DFS(to,x);
                v.push_back(tmp);
            }
            sort(v.begin(),v.end());
            int base=233;
            for(vector<int>::iterator i=v.begin();i!=v.end();i++){
                sum+=(*i)*base%mod;sum%=mod;
                base*=233;base%=mod;
            }
            return sum;
        }
        inline void init(){
            m=I.read();
            for(int i=1;i<=m;i++){
                n=I.read();
                memset(fir,0,sizeof(fir));tot=0;
                for(int x,j=1;j<=n;j++){
                    x=I.read();
                    if(x==0) continue ;
                    add(x,j);add(j,x);
                }
                ans[i][0]=n;
                for(int j=1;j<=n;j++){
                    ans[i][j]=DFS(j,0);
                }
                sort(ans[i]+1,ans[i]+n+1);
                put[i]=i;
                for(int j=1;j<i;j++){
                    if(ans[i][0]==ans[j][0]){
                        int ff=0;
                        for(int k=1;k<=n;k++){
                            if(ans[j][k]==ans[i][k]) ;
                            else{
                                ff=1;
                                break ;
                            }
                        }
                        if(ff==0){
                            put[i]=put[j];
                            break ;
                        }
                    }
                }
            }
            for(int i=1;i<=m;i++) cout<<put[i]<<endl;
        }
}S;
signed main(){S.init();}