树哈希模板

判断树同构。

对于无根树判断树同构，需要每个根都哈希判断。

查看代码

ULL calc (int u, int fa)
{
    sz[u] = 1;
    ULL res = 0;
    vector <ULL> h;
    for (int v : g[u]) if (v ^ fa)
        h.pb(calc(v, u)), sz[u] += sz[v];
    sort(h.begin(), h.end());
    for (int i = 0; i < h.size(); ++i)
        res += h[i] * p[i];
    return res * sz[u] + 1;
}

如果是无根树，需要对于每个点作为根，可以换根DP。

查看代码

void input ()
{
    read(n);
    for (int i = 1; i <= n; ++i)
        e[i].clear(), h[i].clear(), s[i].clear();
    for (int i = 1, a; i <= n; ++i)
    {
        read(a);
        if (a) e[a].pb(i), e[i].pb(a);
    }
}
int calc (int u)
{
    s[u].resize(h[u].size());
    sort(h[u].begin(), h[u].end());
    int res = 0;
    for (int i = 0; i < h[u].size(); ++i)
    {
        int k = (LL)h[u][i] * pbase[i] % mod;
        adj(res += k - mod);
        adj((s[u][i] = k) += (i ? s[u][i - 1] : 0) - mod);
    }
    return (res + 1ll) * sz[u] % mod;
}
void dfs1 (int u)
{
    sz[u] = 1;
    for (int v : e[u]) if (v ^ p[u])
    {
        p[v] = u;
        dfs1(v);
        sz[u] += sz[v];
        h[u].pb(f[v]);
    }
    f[u] = calc(u);
}
void dfs2 (int u)
{
    g[u] = calc(u);
    for (int v : e[u]) if (v ^ p[u])
    {
        int t = lower_bound(h[u].begin(), h[u].end(), f[v]) - h[u].begin();
        sz[u] -= sz[v], sz[v] += sz[u];
        int k = ((t ? s[u][t - 1] : 0) + (LL)(s[u][h[u].size() - 1] - s[u][t]) * ibase + 1) % mod * sz[u] % mod;
        adj(k), h[v].pb(k);
        dfs2(v);
        sz[v] -= sz[u], sz[u] += sz[v];
    }
}
void init () { dfs1(1), dfs2(1); }