bzoj4337 BJOI2015 树的同构

Description

树是一种很常见的数据结构。

我们把N个点，N-1条边的连通无向图称为树。

若将某个点作为根，从根开始遍历，则其它的点都有一个前驱，这个树就成为有根树。

对于两个树T1和T2，如果能够把树T1的所有点重新标号，使得树T1和树T2完全相

同，那么这两个树是同构的。也就是说，它们具有相同的形态。

现在，给你M个有根树，请你把它们按同构关系分成若干个等价类。

n,m<=50

Solution

去年noip就见过的题现在才整出来(lll￢ω￢)

判断树重构可以用树哈希。我们求出树的重心并以重心为根做dfs。规定叶节点哈希值为base^1，然后每个节点把相应的儿子按照哈希值有序来搞搞就行了。哈希的方法包括但不限于：乘质数、自然溢出、双模数

如果给出的树有两个根那么新建一个节点作为根，把连接两个根的边拆掉分别连到新根，然后照做就行了

这是一道模板题

Code

#include <stdio.h>
#include <string.h>
#include <algorithm>
#define rep(i,st,ed) for (int i=st;i<=ed;++i)
#define fill(x,t) memset(x,t,sizeof(x))

typedef unsigned long long LL;
const int N=;
const LL Base=;

struct edge {int x,y,next; bool vis;} e[N*];

int size[N],mx[N],root;
int ls[N],edCnt,n;

LL ans[N],hash[N],vec[N];

int read() {
    int x=,v=; char ch=getchar();
    for (;ch<'0'||ch>'9';v=(ch=='-')?(-):(v),ch=getchar());
    for (;ch<='9'&&ch>='0';x=x*+ch-'0',ch=getchar());
    return x*v;
}

void add_edge(int x,int y) {
    e[++edCnt]=(edge) {x,y,ls[x],}; ls[x]=edCnt;
    e[++edCnt]=(edge) {y,x,ls[y],}; ls[y]=edCnt;
}

void dfs1(int now,int fa) {
    size[now]=; mx[now]=;
    for (int i=ls[now];i;i=e[i].next) {
        if (e[i].y==fa||e[i].vis) continue;
        dfs1(e[i].y,now); size[now]+=size[e[i].y];
        mx[now]=std:: max(mx[now],size[e[i].y]);
    }
    mx[now]=std:: max(mx[now],n-size[now]);
    if (!root||mx[now]<mx[root]) root=now;
}

void dfs2(int now,int fa) {
    for (int i=ls[now];i;i=e[i].next) {
        if (e[i].y==fa||e[i].vis) continue;
        dfs2(e[i].y,now);
    }
    int tmp=;
    for (int i=ls[now];i;i=e[i].next) {
        if (e[i].y==fa||e[i].vis) continue;
        vec[++tmp]=hash[e[i].y];
    }
    std:: sort(vec+,vec+tmp+);
    hash[now]=Base;
    rep(i,,tmp) {
        (((hash[now]*=Base)^=vec[i])+=vec[i])^=vec[i];
    }
}

int main(void) {
    freopen("data.in","r",stdin);
    freopen("myp.out","w",stdout);
    for (int T=read(),now=;T--;++now) {
        fill(ls,); edCnt=; root=;
        n=read();
        rep(i,,n) {
            int fa=read();
            if (fa) add_edge(fa,i);
        }
        dfs1(,);
        int tmp1=,tmp2=;
        rep(i,,n) if (mx[i]==mx[root]) tmp2=tmp1,tmp1=i;
        if (tmp2) {
            rep(i,,edCnt) if (e[i].x==tmp1&&e[i].y==tmp2) {
                e[i].vis=e[i^].vis=;
                break;
            }
            root=n+;
            add_edge(root,tmp1); add_edge(root,tmp2);
        }
        dfs2(root,); ans[now]=hash[root];
        rep(i,,now) if (ans[i]==ans[now]) {
            printf("%d\n", i); break;
        }
    }
    return ;
}