树的同构
两棵树如果形态相同,就称这两棵树同构。
也就是:存在一个排列(p),将其中一棵树的编号(i)改为(p_i),使得这棵树和另外一棵树完全相同。
树hash
判断两棵树是否同构可以使用树hash的方法。用(hs[i])表示i这棵子树的hash值。那么有(hs[u]=1 + sum hs[v]times prime[siz[v]]),(prime[i])表示第(i)个素数。(siz[i])表示以(i)为根的子树的大小。dfs一遍即可求出。
任意点为根的hash值
设(f[i])表示以(i)为根时整棵树的hash值。然后就有(f[v] = (f[u] – hs[v] * prime[siz[v]]) * prime[n-siz[v]] + hs[v])
自上而下转移即可。
以重心为根的hash值
因为一棵树的重心只有一个或者两个。所以可以找到两棵树的中心。以重心为根求树的hash值。
如果存在两个重心。可以新建一个根节点,分别向两个重心连边。并且断掉两个重心之间的边。
例题
luogu5043
判断无根树是否同构,以重心为根即可(分别求出以每个点为根的hash也可)
/* * @author: wxyww * @date: 2020-03-06 16:59:41 * @last modified time: 2020-03-06 17:24:12 */ #include<cstdio> #include<iostream> #include<cstdlib> #include<cmath> #include<map> #include<ctime> #include<bitset> #include<cstring> #include<algorithm> #include<string> #include<queue> #include<vector> using namespace std; typedef long long ll; typedef unsigned long long ull; const int n = 110; ll read() { ll x=0,f=1;char c=getchar(); while(c<'0'||c>'9') { if(c=='-') f=-1; c=getchar(); } while(c>='0'&&c<='9') { x=x*10+c-'0'; c=getchar(); } return x*f; } int pri[n * n],vis[n * n]; void pre() { int tot = 0; for(int i = 2;i <= 10000;++i) { if(!vis[i]) pri[++tot] = i; for(int j = 1;j <= tot && pri[j] * i <= 10000;++j) { vis[pri[j] * i] = 1; if(i % pri[j] == 0) break; } } } vector<int>e[n]; map<ull,int>ma; int siz[n]; ull hs[n]; int n,root1,root2; void dfs(int u,int fa) { siz[u] = 1; for(vector<int>::iterator it = e[u].begin();it != e[u].end();++it) { if((*it == fa) || (*it == root1 && u) || (*it == root2 && u)) continue; dfs(*it,u); hs[u] += hs[*it] * pri[siz[*it]]; siz[u] += siz[*it]; } hs[u]++; } void get1(int u,int fa) { siz[u] = 1; for(vector<int>::iterator it = e[u].begin();it != e[u].end();++it) { if(*it == fa) continue; get1(*it,u); siz[u] += siz[*it]; } } void get2(int u,int fa) { int mx = n - siz[u]; for(vector<int>::iterator it = e[u].begin();it != e[u].end();++it) { if(*it == fa) continue; get2(*it,u); mx = max(mx,siz[*it]); } if(mx <= n / 2) { if(!root1) root1 = u; else root2 = u; } } int main() { pre(); int t = read(); for(int i = 1;i <= t;++i) { memset(hs,0,sizeof(hs)); n = read(); for(int i = 0;i <= n;++i) e[i].clear(); for(int i = 1;i <= n;++i) { int x = read(); if(!x) continue; e[x].push_back(i); e[i].push_back(x); } root1 = 0,root2 = 0; get1(1,0); get2(1,0); e[0].push_back(root1); if(root2) e[0].push_back(root2); dfs(0,0); if(!ma[hs[0]]) ma[hs[0]] = i; printf("%dn",ma[hs[0]]); } return 0; }
luogu4323
求出a中每个点为根的hash值,然后对于b中每个与叶子节点相连的节点,求出减去该节点相连的一个叶子节点之后的hash值。如果与a中某个节点hash值相同,说明该节点相连的叶子节点都是可能被去除的。
/* * @author: wxyww * @date: 2020-03-06 19:31:22 * @last modified time: 2020-03-06 20:03:13 */ #include<cstdio> #include<iostream> #include<cstdlib> #include<cmath> #include<ctime> #include<bitset> #include<cstring> #include<algorithm> #include<map> #include<string> #include<queue> #include<vector> using namespace std; typedef long long ll; typedef unsigned long long ull; const int n = 200010; ll read() { ll x=0,f=1;char c=getchar(); while(c<'0'||c>'9') { if(c=='-') f=-1; c=getchar(); } while(c>='0'&&c<='9') { x=x*10+c-'0'; c=getchar(); } return x*f; } int siz[n]; vector<int>e1[n],e2[n]; map<ull,bool>ma; ull f[n],hs[n]; int vis[n * 10],pri[n * 10]; void pre() { int tot = 0; for(int i = 2;i < n * 10;++i) { if(!vis[i]) pri[++tot] = i; for(int j = 1;j <= tot && pri[j] * i < n * 10;++j) { vis[pri[j] * i] = 1; if(i % pri[j] == 0) break; } } } int n; void dfs1(int u,int fa) { siz[u] = 1; for(vector<int>::iterator it = e1[u].begin();it != e1[u].end();++it) { if(*it == fa) continue; dfs1(*it,u); hs[u] += hs[*it] * pri[siz[*it]]; siz[u] += siz[*it]; } hs[u]++; } void dfs2(int u,int fa) { ma[f[u]] = true; for(vector<int>::iterator it = e1[u].begin();it != e1[u].end();++it) { if(*it == fa) continue; f[*it] = (f[u] - pri[siz[*it]] * hs[*it]) * pri[n - siz[*it]] + hs[*it]; dfs2(*it,u); } } void dfs3(int u,int fa) { siz[u] = 1; for(vector<int>::iterator it = e2[u].begin();it != e2[u].end();++it) { if(*it == fa) continue; dfs3(*it,u); hs[u] += hs[*it] * pri[siz[*it]]; siz[u] += siz[*it]; } hs[u]++; } int ans[n]; void dfs4(int u,int fa) { if(e2[u].size() == 1 && ma[f[u] - 1]) ans[u] = 1; for(vector<int>::iterator it = e2[u].begin();it != e2[u].end();++it) { if(*it == fa) continue; f[*it] = (f[u] - pri[siz[*it]] * hs[*it]) * pri[n + 1 - siz[*it]] + hs[*it]; dfs4(*it,u); } } int main() { n = read(); pre(); for(int i = 1;i < n;++i) { int u = read(),v = read(); e1[u].push_back(v); e1[v].push_back(u); } for(int i = 1;i <= n;++i) { int u = read(),v = read(); e2[u].push_back(v); e2[v].push_back(u); } dfs1(1,0); f[1] = hs[1]; dfs2(1,0); memset(hs,0,sizeof(hs)); memset(f,0,sizeof(f)); dfs3(1,0); f[1] = hs[1]; dfs4(1,0); for(int i = 1;i <= n + 1;++i) { if(ma[f[i] - 2]) { for(vector<int>::iterator it = e2[i].begin();it != e2[i].end();++it) { if(e2[*it].size() == 1) ans[*it] = 1; } } } for(int i = 1;i <= n + 1;++i) { if(ans[i]) { printf("%dn",i);return 0; } } return 0; }
本文来自网络收集,不代表计算机技术网立场,如涉及侵权请联系管理员删除。
ctvol管理联系方式QQ:251552304
本文章地址:https://www.ctvol.com/c-cdevelopment/600365.html