bzoj 4754: [Jsoi2016]独特的树叶树哈希

题目链接：https://www.lydsy.com/JudgeOnline/problem.php?id=4754

我们只需要找到一种方法，可以快速的判断树B删掉一个叶子之后是否与树A同构

最快的方法肯定是判断：以叶子节点的父亲为根时的hash值是否在A中存在

所以我们先求出每个点的子树的hash值，然后再进行换根，记一下前后缀的哈希值就行了

求出A树每个点为根的哈希值后，放进map里记录一下，如果B树删掉了某个叶子之后的值在map中出现了，那么就是我们要找的点

详细的讲解我会另写一篇博客

#include<bits/stdc++.h>

#define base 1011139
#define ll unsigned long long
#define maxn 100010
#define pb push_back

using namespace std;

inline int rd(){
    int x=0,y=1;char c=getchar();
    while(!isdigit(c)){if(c=='-')y=-y;c=getchar();}
    while(isdigit(c))x=x*10+c-'0',c=getchar();
    return x*y;
}

struct node{
    int to;
    ll w,suf;
    node(int x=0,ll y=0,ll z=0){to=x,w=y,suf=z;}
    friend bool operator < (node a,node b){
        return a.w<b.w;
    }
};

int n;
int sz[maxn],du[maxn];
ll bs[maxn],hs[maxn];
vector<int>go[maxn];
vector<node>son[maxn];
map<ll,bool>mp;

inline void init(){
    bs[0]=1;
    for(int i=1; i<=100000; i++)bs[i]=bs[i-1]*base;
    n=rd();
}

inline void read(){
    for(int i=1; i<n; i++){
        int x=rd(),y=rd();
        go[x].pb(y),go[y].pb(x);
        du[x]++,du[y]++;
    }
}

inline void cal_hash(int now,int siz){
    sort(son[now].begin(),son[now].end());
    hs[now]=siz;
    for(int i=0; i<son[now].size(); i++)hs[now]+=bs[i+1]*son[now][i].w;
}

void dfs(int now,int fa){
    sz[now]=1;
    for(int i=0; i<go[now].size(); i++){
        int to=go[now][i];
        if(to==fa)continue;
        dfs(to,now);
        sz[now]+=sz[to];
        son[now].pb(node(to,hs[to],hs[to]));
    }
    cal_hash(now,sz[now]);
}

void change(int now,int fa,ll hs_fa){
    if(fa){
        son[now].pb(node(fa,hs_fa,hs_fa));
        cal_hash(now,n);
    }
    for(int i=son[now].size()-2; i>=0; i--)son[now][i].suf+=son[now][i+1].suf*bs[1];
    ll pre=0;
    son[now].pb(node(0,0,0));
    for(int i=0; i<son[now].size()-1; i++){
        if(son[now][i].to!=fa){
            change(son[now][i].to,now,pre+bs[i+1]*son[now][i+1].suf+n-sz[son[now][i].to]);
        }
        pre+=bs[i+1]*son[now][i].w;
    }
}

void Clear(){
    memset(hs,0,sizeof(hs));
    memset(sz,0,sizeof(sz));
    memset(du,0,sizeof(du));
    for(int i=1; i<=n; i++)go[i].clear(),son[i].clear();
}

inline void work(){
    read();
    dfs(1,0);
    change(1,0,0);
    for(int i=1; i<=n; i++){
        mp[hs[i]]=true;
    }
    Clear(),n++;
    read();
    dfs(1,0);
    change(1,0,0);
    for(int i=1; i<=n; i++){
        if(du[i]!=1)continue;
        if(mp[son[go[i][0]][1].suf*bs[1]+n-1]){
            printf("%d\n",i);
            return;
        }
    }
}

int main(){
    init();
    work();
    
    return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

#include<bits/stdc++.h>

#define base 1011139

#define ll unsigned long long

#define maxn 100010

#define pb push_back

using namespace std;

inline int rd(){

int x=0,y=1;char c=getchar();

while(!isdigit(c)){if(c=='-')y=-y;c=getchar();}

while(isdigit(c))x=x*10+c-'0',c=getchar();

return x*y;

}

struct node{

int to;

ll w,suf;

node(int x=0,ll y=0,ll z=0){to=x,w=y,suf=z;}

friend bool operator < (node a,node b){

return a.w<b.w;

}

};

int n;

int sz[maxn],du[maxn];

ll bs[maxn],hs[maxn];

vector<int>go[maxn];

vector<node>son[maxn];

map<ll,bool>mp;

inline void init(){

bs[0]=1;

for(int i=1; i<=100000; i++)bs[i]=bs[i-1]*base;

n=rd();

}

inline void read(){

for(int i=1; i<n; i++){

int x=rd(),y=rd();

go[x].pb(y),go[y].pb(x);

du[x]++,du[y]++;

}

inline void cal_hash(int now,int siz){

sort(son[now].begin(),son[now].end());

hs[now]=siz;

for(int i=0; i<son[now].size(); i++)hs[now]+=bs[i+1]*son[now][i].w;

}

void dfs(int now,int fa){

sz[now]=1;

for(int i=0; i<go[now].size(); i++){

int to=go[now][i];

if(to==fa)continue;

dfs(to,now);

sz[now]+=sz[to];

son[now].pb(node(to,hs[to],hs[to]));

}

cal_hash(now,sz[now]);

}

void change(int now,int fa,ll hs_fa){

if(fa){

son[now].pb(node(fa,hs_fa,hs_fa));

cal_hash(now,n);

}

for(int i=son[now].size()-2; i>=0; i--)son[now][i].suf+=son[now][i+1].suf*bs[1];

ll pre=0;

son[now].pb(node(0,0,0));

for(int i=0; i<son[now].size()-1; i++){

if(son[now][i].to!=fa){

change(son[now][i].to,now,pre+bs[i+1]*son[now][i+1].suf+n-sz[son[now][i].to]);

}

pre+=bs[i+1]*son[now][i].w;

}

void Clear(){

memset(hs,0,sizeof(hs));

memset(sz,0,sizeof(sz));

memset(du,0,sizeof(du));

for(int i=1; i<=n; i++)go[i].clear(),son[i].clear();

}

inline void work(){

read();

dfs(1,0);

change(1,0,0);

for(int i=1; i<=n; i++){

mp[hs[i]]=true;

}

Clear(),n++;

read();

dfs(1,0);

change(1,0,0);

for(int i=1; i<=n; i++){

if(du[i]!=1)continue;

if(mp[son[go[i][0]][1].suf*bs[1]+n-1]){

printf("%d\n",i);

return;

}

int main(){

init();

work();

return 0;

}

everlasting

bzoj 4754: [Jsoi2016]独特的树叶树哈希

赞过：

相关

《bzoj 4754: [Jsoi2016]独特的树叶树哈希》有1个想法

发表评论取消回复

共享此文章：

赞过：

相关

《bzoj 4754: [Jsoi2016]独特的树叶 树哈希》有1个想法

发表评论 取消回复

《bzoj 4754: [Jsoi2016]独特的树叶树哈希》有1个想法

发表评论取消回复