树的同构

两棵树如果形态相同，就称这两棵树同构。
也就是：存在一个排列(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; }