树的同构
两棵树如果形态相同,就称这两棵树同构。
也就是:存在一个排列,将其中一棵树的编号改为,使得这棵树和另外一棵树完全相同。
树hash
判断两棵树是否同构可以使用树hash的方法。用表示i这棵子树的hash值。那么有,表示第个素数。表示以为根的子树的大小。dfs一遍即可求出。
任意点为根的hash值
设表示以为根时整棵树的hash值。然后就有
自上而下转移即可。
以重心为根的hash值
因为一棵树的重心只有一个或者两个。所以可以找到两棵树的中心。以重心为根求树的hash值。
如果存在两个重心。可以新建一个根节点,分别向两个重心连边。并且断掉两个重心之间的边。
例题
判断无根树是否同构,以重心为根即可(分别求出以每个点为根的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("%d\n",ma[hs[0]]); } return 0; }
求出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("%d\n",i);return 0; } } return 0; }