P5043 【模板】树同构（[BJOI2015]树的同构 // P4323 [JSOI2016]独特的树叶

一、P5043 【模板】树同构（[BJOI2015]树的同构）：

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<string>
#include<vector>
#include<map>
#include<set>
#include<cmath>
#include<queue>
#define ll long long
#define pr make_pair
#define pb push_back
#define lc (cnt<<1)
#define rc (cnt<<1|1)
using namespace std;
const int inf=0x3f3f3f3f;
const ll lnf=0x3f3f3f3f3f3f3f3f;
const double dnf=1e15;
const int mod=1e9+7;
const int maxn=55;
int head[maxn],ver[maxn<<1],nt[maxn<<1];
int n[maxn],si[maxn],tot=1;
unsigned ll ha[maxn][maxn],f[maxn];
int p[]={ 
   0,2,3,5,7,11,13,17,19,23,29,31,37,
         41,43,47,53,59,61,67,71,73,79,83,89,97,
         101,103,107,109,113,127,131,137,139,149,
         151,157,163,167,173,179,181,191,193,197,
         199,211,223,227,229};

void init(void)
{ 
   
    memset(head,0,sizeof(head));
    tot=1;
}

void add(int x,int y)
{ 
   
    ver[++tot]=y,nt[tot]=head[x],head[x]=tot;
}

void dfs(int x,int fa)
{ 
   
    f[x]=si[x]=1;
    for(int i=head[x];i;i=nt[i])
    { 
   
        int y=ver[i];
        if(y==fa) continue;
        dfs(y,x);
        f[x]+=f[y]*p[si[y]];
        si[x]+=si[y];
    }
}

bool check(int i,int j)
{ 
   
    for(int k=1;k<=n[i];k++)
    { 
   
        if(ha[i][k]!=ha[j][k]) return false;
    }
    return true;
}

int main(void)
{ 
   
    int m,fa;
    scanf("%d",&m);
    for(int i=1;i<=m;i++)
    { 
   
        init();
        scanf("%d",&n[i]);
        for(int j=1;j<=n[i];j++)
        { 
   
            scanf("%d",&fa);
            if(fa) add(fa,j),add(j,fa);
        }
        for(int j=1;j<=n[i];j++)
        { 
   
            dfs(j,0);
            ha[i][j]=f[j];
        }
        sort(ha[i]+1,ha[i]+n[i]+1);
    }
    for(int i=1;i<=m;i++)
    { 
   
        bool flag=true;
        for(int j=1;j<=i;j++)
        { 
   
            if(n[i]==n[j]&&check(i,j))
            { 
   
                printf("%d\n",j);
                flag=false;
                break;
            }
        }
        if(flag)
            printf("%d\n",i);
    }
    return 0;
}

二、P4323 [JSOI2016]独特的树叶：

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<string>
#include<vector>
#include<map>
#include<set>
#include<cmath>
#include<queue>
#define ll long long
#define llu unsigned ll
#define pr make_pair
#define pb push_back
#define lc (cnt<<1)
#define rc (cnt<<1|1)
using namespace std;
const int inf=0x3f3f3f3f;
const ll lnf=0x3f3f3f3f3f3f3f3f;
const double dnf=1e15;
const int mod=1e9+7;
const int maxn=1000100;
int head[maxn],ver[maxn],nt[maxn],d[maxn];
int fa[maxn],si[maxn],tot=1,n;
llu g[maxn],f[maxn];
int p[maxn<<1],cnt=0;
bool ha[maxn<<1];
set<llu> se;

void prime(void)
{ 
   
    ha[1]=true;
    for(int i=2;i<(maxn<<1);i++)
    { 
   
        if(!ha[i]) p[++cnt]=i;
        for(int j=1;j<=cnt&&i*p[j]<(maxn<<1);j++)
        { 
   
            ha[i*p[j]]=true;
            if(i%p[j]==0) break;
        }
    }
}

void init(void)
{ 
   
    memset(head,0,sizeof(head));
    tot=1;
    n++;
}

void add(int x,int y)
{ 
   
    ver[++tot]=y,nt[tot]=head[x],head[x]=tot;
}

void dfs1(int x,int ff)
{ 
   
    f[x]=si[x]=1;
    for(int i=head[x];i;i=nt[i])
    { 
   
        int y=ver[i];
        if(y==ff) continue;
        dfs1(y,x);
        f[x]+=f[y]*p[si[y]];
        si[x]+=si[y];
    }
}

void dfs2(int x,int ff)
{ 
   
    for(int i=head[x];i;i=nt[i])
    { 
   
        int y=ver[i];
        if(y==ff) continue;
        g[y]=f[y]+(g[x]-f[y]*p[si[y]])*p[n-si[y]];
        dfs2(y,x);
    }
}


int main(void)
{ 
   
    prime();
    scanf("%d",&n);
    int x,y;
    for(int i=1;i<n;i++)
    { 
   
        scanf("%d%d",&x,&y);
        add(x,y);
        add(y,x);
    }
    dfs1(1,0);
    g[1]=f[1];
    dfs2(1,0);
    for(int i=1;i<=n;i++)
        se.insert(g[i]);

    init();
    for(int i=1;i<n;i++)
    { 
   
        scanf("%d%d",&x,&y);
        d[x]++,d[y]++;
        add(x,y);
        add(y,x);
        fa[x]=y,fa[y]=x;//注意这里叶子节点怎么找它的上一节点
    }
    dfs1(1,0);
    g[1]=f[1];
    dfs2(1,0);

    for(int i=1;i<=n;i++)
    { 
   
        if(d[i]==1&&se.find(g[fa[i]]-p[1])!=se.end())
        { 
   
            printf("%d\n",i);
            break;
        }
    }

    return 0;
}