4337: BJOI2015 树的同构

题解：

树的同构的判定

有根树从根开始进行树hash

先把儿子的f进行排序

$f[i]=sum_{j=1}^{k} { f[j]*prime[j]} +num[i]$（我没有仔细想这样是不是树是唯一的。。。反正过了）

无根树先找到重心再作为根

因为重心最多只有两个，复杂度仍旧O(n)

代码：

#include <bits/stdc++.h>
using namespace std;
#define rint register int
#define IL inline
#define rep(i,h,t) for (int i=h;i<=t;i++)
#define dep(i,t,h) for (int i=t;i>=h;i--)
#define me(x) memset(x,0,sizeof(x))
#define ll long long
#define mep(x,y) memcpy(x,y,sizeof(y))
#define mid ((h+t)>>1)
#define ull unsigned ll
namespace IO{
    char ss[1<<24],*A=ss,*B=ss;
    IL char gc()
    {
        return A==B&&(B=(A=ss)+fread(ss,1,1<<24,stdin),A==B)?EOF:*A++;
    }
    template<class T>void read(T &x)
    {
        rint f=1,c; while (c=gc(),c<48||c>57) if (c=='-') f=-1; x=(c^48);
        while (c=gc(),c>47&&c<58) x=(x<<3)+(x<<1)+(c^48); x*=f;
    }
    char sr[1<<24],z[20]; int Z,C=-1;
    template<class T>void wer(T x)
    {
        if (x<0) sr[++C]='-',x=-x;
        while (z[++Z]=x%10+48,x/=10);
        while (sr[++C]=z[Z],--Z);
    }
    IL void wer1() { sr[++C]=' ';}
    IL void wer2() { sr[++C]='
';}
    template<class T>IL void maxa(T &x,T y) { if (x<y) x=y;} 
    template<class T>IL void mina(T &x,T y) { if (x>y) x=y;}
    template<class T>IL T MAX(T x,T y) {return x>y?x:y;}
    template<class T>IL T MIN(T x,T y) {return x<y?x:y;}
};
using namespace IO;
const int N=100;
int head[N],n,m,l,num[N],f[N];
struct re{
    int a,b;
}e[N*2];
bool q[1100];
int zs[N];
ull son[N][N],ans[N],g[N];
IL void arr(int x,int y)
{
    e[++l].a=head[x];
    e[l].b=y;
    head[x]=l;
}
void fdrt(int x,int y)
{
    num[x]=1;
    for (rint u=head[x];u;u=e[u].a)
    {
        int v=e[u].b;
        if (v!=y)
        {
            fdrt(v,x);
            num[x]+=num[v];
            if (num[v]>f[x]) f[x]=num[v];
        }
    }
    if (n-num[x]>f[x]) f[x]=n-num[x];
}
void dfs(int x,int y)
{
    num[x]=1;
    int cnt=0;
    for (rint u=head[x];u;u=e[u].a)
    {
        int v=e[u].b;
        if (v!=y)
        {
            dfs(v,x);
            son[x][++cnt]=g[v];
            num[x]+=num[v];
        }
    }
    sort(son[x]+1,son[x]+cnt+1);
    ull now=0;
    rep(i,1,cnt) now=now+son[x][i]*zs[i];
    now+=num[x];
    g[x]=now;
}
int main()
{
    freopen("1.in","r",stdin);
    freopen("1.out","w",stdout);
    read(m);
    rep(i,2,1000)
      for (int j=2;j*i<=1000;j++)
        q[i*j]=1;
    int cnt=0;
    rep(i,501,1000)
      if (!q[i])
      {
          zs[++cnt]=i;
          if (cnt>=60) break;
      }
    rep(j,1,m)
    {
        me(head); read(n); me(f); l=0;
        rep(i,1,n)
        {
            int x,y; read(x);
            if (x) arr(x,i),arr(i,x);
        }
        fdrt(1,0);
        int ma=1e9;
        rep(i,1,n) ma=min(ma,f[i]);
        rep(i,1,n)
          if (f[i]==ma)
          {
               dfs(i,0); maxa(ans[j],g[i]);
          }
    }
    rep(i,1,m)
      rep(j,1,m)
        if(ans[j]==ans[i])
        {
            cout<<j<<endl; break;
        }
    return 0; 
}