[BZOJ4754/Luogu4323][JSOI2016]独特的树叶(树Hash)

发布于 2018-05-24  124 次阅读


本文章由SYCstudio或本站其它作者所有,严禁转载,转载必究

本文链接地址:[BZOJ4754/Luogu4323][JSOI2016]独特的树叶(树Hash)

Description

JYY有两棵树A和B:树A有N个点,编号为1到N;树B有N+1个点,编号为1到N+1。JYY知道树B恰好是由树A加上一个叶节点,然后将节点的编号打乱后得到的。他想知道,这个多余的叶子到底是树B中的哪一个叶节点呢?

Tag

树Hash

解决思路

此题关键在于如何快速判断两个树是否同构。这里采用树$Hash$的方式。
先把第一棵树$Hash$出来,求出以任意一个点为根时的$hash$值。可以先选取一个点出发,求出以这个点为根时每一个点子树内的$hash$值,然后再从上向下传递一边,求出以每一个点为根的$hash$值。用$Map$记录下第一棵树中出现过的$Hash$值。
然后用同样的$Hash$方式,求出第二棵树上的$Hash$值,由于选择的点一定是叶子节点,所以求出分别去掉每一个叶子节点后的$Hash$值,在$Map$中进行查找。
由于有子树的关系,又因为要快速向下传递,这里采用异或和加权的方式求$Hash$,具体参见代码。

代码

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<map>
using namespace std;

#define ll long long
#define ull unsigned long long
#define mem(Arr,x) memset(Arr,x,sizeof(Arr))

const int maxN=100010;
const int maxM=maxN*2;
const ull base1=50;
const ull base2=20020729;
const int inf=2147483647;

int n;
int edgecnt,Head[maxN],Next[maxM],V[maxM];
ull Hash[maxN];
int Size[maxN],Degree[maxN];
int Ans=inf;
map<ull,bool> Get;

void Add_Edge(int u,int v);
void Build(int u,int fa);
void Calc(int u,int fa);
void GetAns(int u,int fa);

int main()
{
    mem(Head,-1);
    scanf("%d",&n);
    for (int i=1;i<n;i++)
    {
        int u,v;scanf("%d%d",&u,&v);
        Add_Edge(u,v);Add_Edge(v,u);
    }
    Build(1,0);
    Calc(1,0);
    edgecnt=0;mem(Head,-1);mem(Hash,0);mem(Size,0);n++;
    for (int i=1;i<n;i++)
    {
        int u,v;scanf("%d%d",&u,&v);
        Add_Edge(u,v);Add_Edge(v,u);
        Degree[u]++;Degree[v]++;
    }
    for (int i=1;i<=n;i++)
        if (Degree[i]>1)
        {
            Build(i,0);
            GetAns(i,0);
            break;
        }
    printf("%d\n",Ans);
    return 0;
}

void Add_Edge(int u,int v)
{
    edgecnt++;Next[edgecnt]=Head[u];Head[u]=edgecnt;V[edgecnt]=v;
    return;
}

void Build(int u,int fa)
{
    Size[u]=1;
    for (int i=Head[u];i!=-1;i=Next[i])
        if (V[i]!=fa)
        {
            Build(V[i],u);
            Hash[u]=Hash[u]^(Hash[V[i]]+base1);
            Size[u]+=Size[V[i]];
        }
    Hash[u]=Hash[u]+base2*Size[u]+1;
    return;
}

void Calc(int u,int fa)
{
    Get[Hash[u]]=1;
    for (int i=Head[u];i!=-1;i=Next[i])
        if (V[i]!=fa)
        {
            ull tmp=((Hash[u]-(ull)n*base2-1)^(Hash[V[i]]+base1))+(ull)(n-Size[V[i]])*base2+1;
            Hash[V[i]]=((Hash[V[i]]-(ull)Size[V[i]]*base2-1)^(tmp+base1))+(ull)n*base2+1;
            Size[V[i]]=n;
            Calc(V[i],u);
        }
    return;
}

void GetAns(int u,int fa)
{
    for (int i=Head[u];i!=-1;i=Next[i])
        if (V[i]!=fa)
        {
            if (Degree[V[i]]>1)
            {
                ull tmp=((Hash[u]-base2*n-1)^(Hash[V[i]]+base1))+(n-Size[V[i]])*base2+1;
                Hash[V[i]]=((Hash[V[i]]-base2*Size[V[i]]-1)^(tmp+base1))+base2*n+1;
                Size[V[i]]=n;
                GetAns(V[i],u);
            }
            else
            {
                ull tmp=((Hash[u]-base2*n-1)^(Hash[V[i]]+base1))+(n-1)*base2+1;
                if (Get.count(tmp)) Ans=min(Ans,V[i]);
            }
        }
    return;
}

本文章由SYCstudio或本站其它作者所有,严禁转载,转载必究

本文链接地址:[BZOJ4754/Luogu4323][JSOI2016]独特的树叶(树Hash)


HNCJ OIer 一枚