树hash

树的同构

两棵树如果形态相同，就称这两棵树同构。
也就是：存在一个排列\(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("%d\n",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("%d\n",i);return 0;
        }
    }
    return 0;
}

原文链接:https://www.cnblogs.com/wxyww/p/treehash.html
如有疑问请与原作者联系

标签：

版权申明：本站文章部分自网络，如有侵权，请联系：west999com@outlook.com
特别注意：本站所有转载文章言论不代表本站观点，本站所提供的摄影照片，插画，设计作品，如需使用，请与原作者联系，版权归原作者所有