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 ;
}