题目链接:https://www.lydsy.com/JudgeOnline/problem.php?id=4754
我们只需要找到一种方法,可以快速的判断树B删掉一个叶子之后是否与树A同构
最快的方法肯定是判断:以叶子节点的父亲为根时的hash值是否在A中存在
所以我们先求出每个点的子树的hash值,然后再进行换根,记一下前后缀的哈希值就行了
求出A树每个点为根的哈希值后,放进map里记录一下,如果B树删掉了某个叶子之后的值在map中出现了,那么就是我们要找的点
详细的讲解我会另写一篇博客
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 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; } |
《bzoj 4754: [Jsoi2016]独特的树叶 树哈希》有1个想法