P5043 【模板】树同构（[BJOI2015]树的同构）

Cht_master · 2021-10-14 23:11:22 · 题解

提供一种在 n=10^5 的级别也很难出现错误的哈希计算公式：

注意以 u 为根的子树指以 1 为起点遍历时 u 的子树；而以 u 为根时的全树指以 u 为起点遍历整棵树。

令 f(u) 表示以结点 u 为根的子树对应的哈希值，g(u) 表示 u 为根时全树的哈希值；size(u) 为以 u 为根的子树的大小，fa(u) 为 u 的父亲；prime(i) 指第 i 个质数。计算公式为：

f(u)=\sum_{v\in son(u)}f(v)\cdot prime(size(v))\\ g(u)=prime(siz(1)-siz(u))\cdot(g(fa(u))-f(u)\cdot prime(size(u)))+f(u)

其中 f(u) 就能满足一般的树同构的判断了。g(u) 的计算用换根 DP 实现。
最后需要尤其注意 g(T1)=g(T2) 但 size(T1)\not =size(T2) 的情况是存在的，所以需要在最后特判一下。
如果仍然觉得判断不准确，可以对树的两个重心（如果有两个重心）分别进行 DP 然后看哈希值一不一样；在此的基础上再用双哈希。
利用 set 实现 \text{Two Point} 的复杂度为 O(nm\log_2n)；若再利用哈希判断优化可以做到 O(nm)。

#include<bits/stdc++.h>
#define ull unsigned long long
using namespace std;
const int mxNM(5e1);
namespace Prm{//埃氏筛足矣.
    int cnt,Is[23005],prm[mxNM*mxNM+5];
    void Art_scan(int R){
        for(int i(0);i<=R;++i)Is[i]=-1;
        for(int i(2);i<=R;++i)if(Is[i]==-1){
            Is[i]=1,prm[++cnt]=i;
            for(int j(i<<1);j<=R;j+=i)Is[j]=0;
        }
    }
}
namespace Trees{
    int m;//m个树.
    struct Tree{
        int fa[mxNM+5],siz[mxNM+5];
        vector<int>nd[mxNM+5];
        ull f[mxNM+5],g[mxNM+5];//令f(u)表示以结点u为根的子树对应的哈希值,g(u)表示u为根时全树的哈希值.
        void add(int u,int v){if(u&&v)nd[u].push_back(v);}//不更新0结点.
        void dfs1(int u,int pre){//计算f(u).
            fa[u]=pre,siz[u]=f[u]=1;
            for(int i(0),v;i<nd[u].size();++i){
                v=nd[u][i];if(v==pre)continue;
                dfs1(v,u),siz[u]+=siz[v],f[u]=f[u]+(1ull)*f[v]*Prm::prm[siz[v]];
            }
        }
        void dfs2(int u){//计算g(u).
            g[u]=Prm::prm[siz[1]-siz[u]]*(g[fa[u]]-f[u]*Prm::prm[siz[u]])+f[u];
            for(int i(0),v;i<nd[u].size();++i)if(nd[u][i]!=fa[u])dfs2(nd[u][i]);
        }
    }tr[mxNM+5];
    void sol(){
        for(int i(1);i<=m;++i)tr[i].dfs1(1,0);
        for(int i(1);i<=m;++i)tr[i].dfs2(1);
        for(int T1(1);T1<=m;++T1){//Two Point.
            set<ull>s;s.clear();
            for(int u(1);u<=tr[T1].siz[1];++u)s.insert(tr[T1].g[u]);
            for(int T2(1),F(0);T2<=m;++T2){
                for(int u(1);u<=tr[T2].siz[1];++u)
                    if(tr[T1].siz[1]==tr[T2].siz[1]&&s.find(tr[T2].g[u])!=s.end()){F=1,printf("%d\n",T2);break;}//记得特判树的大小.
                if(F)break;
            }
        }
    }
}
int main(){
    Prm::Art_scan(23000);//大约要算到23000.
    scanf("%d",&Trees::m);
    for(int i(1),n;i<=Trees::m;++i){
        scanf("%d",&n);
        for(int u,v(1);v<=n;++v)scanf("%d",&u),Trees::tr[i].add(u,v),Trees::tr[i].add(v,u);
    }
    Trees::sol();
    return 0;
}