发布时间：2024-09-12

树哈希

CF1800G

题意：

判断树是否是对称的

做法一：随机种子+shift

mt19937_64 rng(time(0));
ULL shift(ULL x){
    x^=x<<13,x^=x>>7,x^=x<<17;
    return x;
}
void solve(){   
    int n;
    cin>>n;
    vector<int> adj[n+1];
    for(int i=1;i<n;i++){
        int u,v;
        cin>>u>>v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    ULL seed=rng();
    vector<int> sym(n+1);
    vector<ULL> h(n+1);
    function<void(int,int)> dfs=[&](int u,int fa){
        ULL sum=seed,xsum=0;
        for(auto v:adj[u]){
            if(v==fa)continue;
            dfs(v,u);
            sum+=shift(h[v]),xsum^=shift(h[v]);
        }
        h[u]=sum;
        if(!xsum){
            sym[u]=1;
            return;
        }
        for(auto v:adj[u]){
            if(v==fa)continue;
            if(xsum==shift(h[v])&&sym[v]){
                sym[u]=1;
                return;
            }
        }
    };
    dfs(1,0);
    cout<<(sym[1]?"YES\n":"NO\n");
}

做法二：AHU算法 $O(nlogn)$

• 严格正确
• 使用map<vector<int>,int>

void solve(){   
    int n;
    cin>>n;
    vector<int> adj[n+1];
    for(int i=1;i<n;i++){
        int u,v;
        cin>>u>>v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    map<vector<int>,int> mp;
    vector<int> h(n+1),sym(n+1);
    int idx=0;
    auto get=[&](vector<int> &v){
        if(!mp.count(v))mp[v]=++idx;
        return mp[v];
    };
    function<void(int,int)> dfs=[&](int u,int fa){
        vector<int> tmp;
        map<int,int> cnt;
        for(auto v:adj[u]){
            if(v==fa)continue;
            dfs(v,u);
            tmp.push_back(h[v]);
        }
        sort(tmp.begin(),tmp.end());
        h[u]=get(tmp);
        for(auto v:adj[u]){
            if(v==fa)continue;
            cnt[h[v]]++;
        }
        int cur=0,p;
        for(auto [x,y]:cnt){
            if(y&1)cur++,p=x;
        }
        if(!cur){
            sym[u]=1;
            return;
        }
        if(cur==1){
            for(auto v:adj[u]){
                if(v==fa)continue;
                if(h[v]==p&&sym[v]){
                    sym[u]=1;
                    return;
                }
            }
        }
    };
    dfs(1,0);
    cout<<(sym[1]?"YES\n":"NO\n");
}

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

• 判断两棵无根树是否相等
• 有根树可以直接跑，无根树找重心，若重心两个则跑两次

AHU算法

map<vector<int>,int> mp;
int idx=0;
int get(vector<int> &v){
    if(!mp.count(v))mp[v]=++idx;
    return mp[v];
}
PII cal(){   
    int n;
    cin>>n;
    vector<int> adj[n+1];
    for(int i=1;i<=n;i++){
        int fa;
        cin>>fa;
        if(fa){
            adj[fa].push_back(i);
            adj[i].push_back(fa);
        }
    }
    vector<int> h(n+1);
    int rt=0,rrt=0,mxsiz=1e9;
    function<int(int,int)> get_size=[&](int u,int fa){
        int sz=1;
        for(auto v:adj[u]){
            if(v==fa)continue;
            sz+=get_size(v,u);
        }
        return sz;
    };
    function<int(int,int,int)> get_wc=[&](int u,int fa,int tot){
        int sum=1,ms=0;
        for(auto v:adj[u]){
            if(v==fa)continue;
            int t=get_wc(v,u,tot);
            sum+=t;
            ms=max(ms,t);
        }
        ms=max(ms,tot-sum);
        if(ms<mxsiz)mxsiz=ms,rt=u,rrt=0;
        else if(ms==mxsiz)rrt=u;
        return sum;
    };
    function<void(int,int)> dfs=[&](int u,int fa){
        vector<int> tmp;
        map<int,int> cnt;
        for(auto v:adj[u]){
            if(v==fa)continue;
            dfs(v,u);
            tmp.push_back(h[v]);
        }
        sort(tmp.begin(),tmp.end());
        h[u]=get(tmp);
        for(auto v:adj[u]){
            if(v==fa)continue;
            cnt[h[v]]++;
        }
        int cur=0,p;
        for(auto [x,y]:cnt){
            if(y&1)cur++,p=x;
        }
    };
    get_wc(1,0,get_size(1,0));
    dfs(rt,0);
    int x=h[rt],y=0;
    h.assign(n+1,0);
    if(rrt){
        dfs(rrt,0);
        y=h[rrt];
    }
    if(x>y)swap(x,y);
    return {x,y};
}
void solve(){
    int m;
    cin>>m;
    vector<PII> ans(m+1);
    for(int i=1;i<=m;i++){
        ans[i]=cal();
        for(int j=1;j<=m;j++){
            if(ans[j]==ans[i]){
                cout<<j<<"\n";
                break;
            }
        }
    }
}

普通异或哈希做法

mt19937_64 rng(time(0));
ULL shift(ULL x){
    x^=x<<13,x^=x>>7,x^=x<<17;
    return x;
}
ULL seed;
PII cal(){   
    int n;
    cin>>n;
    vector<int> adj[n+1];
    for(int i=1;i<=n;i++){
        int fa;
        cin>>fa;
        if(fa){
            adj[fa].push_back(i);
            adj[i].push_back(fa);
        }
    }
    vector<ULL> h(n+1);
    int rt=0,rrt=0,mxsiz=1e9;
    function<int(int,int)> get_size=[&](int u,int fa){
        int sz=1;
        for(auto v:adj[u]){
            if(v==fa)continue;
            sz+=get_size(v,u);
        }
        return sz;
    };
    function<int(int,int,int)> get_wc=[&](int u,int fa,int tot){
        int sum=1,ms=0;
        for(auto v:adj[u]){
            if(v==fa)continue;
            int t=get_wc(v,u,tot);
            sum+=t;
            ms=max(ms,t);
        }
        ms=max(ms,tot-sum);
        if(ms<mxsiz)mxsiz=ms,rt=u,rrt=0;
        else if(ms==mxsiz)rrt=u;
        return sum;
    };
    function<void(int,int)> dfs=[&](int u,int fa){
        ULL sum=seed,xsum=0;
        for(auto v:adj[u]){
            if(v==fa)continue;
            dfs(v,u);
            sum+=shift(h[v]),xsum^=shift(h[v]);
        }
        h[u]=sum;
    };
    get_wc(1,0,get_size(1,0));
    dfs(rt,0);
    int x=h[rt],y=0;
    h.assign(n+1,0);
    if(rrt){
        dfs(rrt,0);
        y=h[rrt];
    }
    if(x>y)swap(x,y);
    return {x,y};
}
void solve(){
    int m;
    cin>>m;
    seed=rng();
    vector<PII> ans(m+1);
    for(int i=1;i<=m;i++){
        ans[i]=cal();
        for(int j=1;j<=m;j++){
            if(ans[j]==ans[i]){
                cout<<j<<"\n";
                break;
            }
        }
    }
}