bzoj4337:BJOI2015 树的同构(树的最小表示+hash)

Author Avatar
Sakits 3月 19, 2018

题解

  判断树的同构题…
  这题数据范围是真的小,其实判断两棵树是否同构可以做到O(nlogn)O(nlogn)
  题目说是有根树只是数据给定有根树而已,但是题面描述的判断是否同构的方法却是无根树的判断方法2333323333
  首先需要知道一个性质,两棵同构的树同样的起点的最小表示肯定是一样的。那么因为两棵同构的树的重心一定是一样的,所以我们只需要求从重心开始的最小表示法就好了。
  树的表示就是入栈出栈序即括号序列,求树的最小表示的方法可以用hash,每次将所有儿子的hash值从小到大排序,接起来然后左右两边加括号,括号用1122表示就好了,然后就可以得到这棵子树的最小表示了。
  判断两棵树是否同构只要判断它们重心出发的最小表示的hash值是否一样即可,若有两个重心则取hash值大的来比较。
  一开始base设为1010一直过不了,吸取教训以后base一定要用个质数,比如233233

代码

#include<iostream>
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<algorithm>
#define ull unsigned long long
using namespace std;
const int maxn=500010, inf=1e9;
struct poi{int too, pre;}e[maxn];
int n, m, cnt, tot, MX, x, root;
int last[maxn], mx[maxn], size[maxn];
ull hs[maxn], HS[maxn], q[maxn], mul[maxn];
inline void read(int &k)
{
    int f=1; k=0; char c=getchar();
    while(c<'0' || c>'9') c=='-' && (f=-1), c=getchar();
    while(c<='9' && c>='0') k=k*10+c-'0', c=getchar();
    k*=f;
}
inline void add(int x, int y){e[++tot]=(poi){y, last[x]}; last[x]=tot;}
void getroot(int x, int fa)
{
    size[x]=1; mx[x]=0;
    for(int i=last[x], too;i;i=e[i].pre)
    if((too=e[i].too)!=fa)
    {
        getroot(too, x);
        size[x]+=size[too];
        mx[x]=max(mx[x], size[too]);
    }
    mx[x]=max(mx[x], n-size[x]);
    MX=min(MX, mx[x]);
}
inline bool cmp(int a, int b){return HS[a]<HS[b];}
void dfs(int x, int fa)
{
    HS[x]=1; size[x]=1;
    for(int i=last[x], too;i;i=e[i].pre)
    if((too=e[i].too)!=fa) dfs(too, x), size[x]+=size[too];
    int cnt=0;
    for(int i=last[x], too;i;i=e[i].pre)
    if((too=e[i].too)!=fa) q[++cnt]=too;
    sort(q+1, q+1+cnt, cmp);
    for(int i=1;i<=cnt;i++) HS[x]=HS[x]*mul[size[q[i]]<<1]+HS[q[i]];
    HS[x]=HS[x]*233;
}
int main()
{
    read(m); mx[0]=inf;
    mul[0]=1; for(int i=1;i<=110;i++) mul[i]=mul[i-1]*233;
    for(int i=1;i<=m;i++)
    {
        read(n); MX=inf;
        memset(last, 0, (n+1)<<2); tot=0;
        for(int j=1;j<=n;j++) 
        {
            read(x);
            if(!x) root=j;
            else add(x, j), add(j, x);
        }
        getroot(root, 0);
        for(int j=1;j<=n;j++)
        if(mx[j]==MX) dfs(j, 0), hs[i]=max(hs[i], HS[j]);
    }
    for(int i=1;i<=m;i++)
    {
        for(int j=1;j<=i;j++)
        if(hs[i]==hs[j]) 
        {
            printf("%d\n", j); 
            break;
        }
    }
}