无根树的同构

Problem

B 树是 A 树添加一个叶子节点并且打乱点编号顺序输出，删除编号最小的叶子节点使得 B 与 A 同构。

Solution

对树进行 hash

具体怎么 hash 这里讲的很清楚：https://www.luogu.org/blog/rabbithu/solution-p4323

基本上不会碰撞吧...?

几点要注意的地方，写在了代码里。
具体来说：点数记得 +1，数组记得清空，后缀 hash 记得初始化一个 0....

Code

// Code by ajcxsu
// Problem: leaves

#include<bits/stdc++.h>
#define MOD (1000000009ll)
using namespace std;
typedef long long ll;

const int N=1e5+10, M=4e5+10, W=233;
int h1[N], h2[N], to[M], nexp[M], p=1;
int deg[N];
inline void ins(int h[], int a, int b) { nexp[p]=h[a], h[a]=p, to[p]=b, p++; }
ll f[N], g[N], pl[N], r[N];
int siz[N];
vector<ll> v1[N], v2;
set<ll> ha;
ll hal[N], har[N];

int ans=0x3f3f3f3f;
void dfs1(int h[], int x, int fr) {
    f[x]=0; // important
    v1[x].clear();
    siz[x]=1;
    for(int u=h[x];u;u=nexp[u])
        if(to[u]!=fr) {
            dfs1(h, to[u], x);
            v1[x].push_back(f[to[u]]), siz[x]+=siz[to[u]];
        }
    if(v1[x].empty()) { f[x]=1; return; }
    sort(v1[x].begin(), v1[x].end());
    for(int i=0, j=v1[x].size(); i<j; i++)
        f[x]=(f[x]*W+v1[x][i])%MOD;
    f[x]=f[x]*siz[x]%MOD;
}
int n, u, v;
void dfs2(int h[], int x, int fr, char con=0) {
    v2.clear();
    if(fr) v2.push_back(g[x]);
    for(int u=h[x];u;u=nexp[u])
        if(to[u]!=fr) v2.push_back(f[to[u]]);
    sort(v2.begin(), v2.end());
    int len=v2.size();
    for(int i=1;i<=len;i++) hal[i]=(hal[i-1]*W+v2[i-1]) % MOD;
    har[len+1]=0; // important
    for(int i=len;i>=1;i--) har[i]=(har[i+1]+v2[i-1]*pl[len-i]) % MOD;
    r[x]=hal[len];
    if(con) ha.insert(r[x]*n%MOD);
    else if(deg[x]==1 && ((fr && ha.count(g[x])) || (!fr && ha.count(f[to[h[x]]]))))
        ans=min(ans, x);
    for(int u=h[x];u;u=nexp[u])
        if(to[u]!=fr) {
            int k=lower_bound(v2.begin(), v2.end(), f[to[u]])-v2.begin();
            g[to[u]]=(n-siz[to[u]])*(hal[k]*pl[len-k-1]%MOD+har[k+2])%MOD;
            if(len==1) g[to[u]]=1;
        }
    for(int u=h[x];u;u=nexp[u])
        if(to[u]!=fr) dfs2(h, to[u], x, con);
}

int main() {
    ios::sync_with_stdio(false);
    pl[0]=1;
    for(int i=1;i<N;i++) pl[i]=(pl[i-1]*W)%MOD;
    cin>>n;
    for(int i=1;i<n;i++) cin>>u>>v, ins(h1, u, v), ins(h1, v, u);
    for(int i=1;i<=n;i++) cin>>u>>v, ins(h2, u, v), ins(h2, v, u), deg[u]++, deg[v]++;
    dfs1(h1, 1, 0), dfs2(h1, 1, 0, 1), n++;
    dfs1(h2, 1, 0), dfs2(h2, 1, 0);
    cout<<ans<<endl;
    return 0;
}

本文链接：https://pst.iorinn.moe/archives/sol-luogu-4323.html
许可： https://pst.iorinn.moe/license.html
若无特别说明，博客内的文章默认将采用 CC BY 4.0 许可协议 进行许可☆