树同构

介绍

两个树同构 $\iff$ 有且仅有一种重新编号方式，使得一棵树的节点重新编号后得到另外一棵树。

• 如果是有根树同构，那么还要额外加一个限制条件：树的节点重新编号，必须让 $r_1$ 映射到 $r_2$，其中 $r_1,r_2$ 为这两棵树的根。

哈希方法

树哈希的方法有很多种，这里提供一位黑红老哥的方法：

对于一棵以 $u$ 为根的子树，假设儿子是 $v_1,v_2,…,v_k$，定义子树的哈希

$$h(u) = 1 + \sum\limits_{i \in [1,k]} f(h(v_i))$$

其中 $h(v_i)$ 是 $v_i$ 对应子树的哈希，$f$ 为一个待定函数。

代码

mt19937 rng((uint32_t)chrono::steady_clock::now().time_since_epoch().count());
ull h[maxn], base = rng();
ull H(ull x){
	return x*x*x*19890535+19260817;
}
ull F(ull x){
	return H(x&((1ll<<32)-1))+H(x>>32);
}
void dfs2(int u, int p, int f) {
    h[u] = base;
    for (int e = head[u]; e; e = edges[e].nxt) {
        int v = edges[e].to;
        if (v == p || v == f) continue;
        dfs2(v, u, f);
        h[u] += F(h[v]);
    }
}

树同构的判断方式

判断两棵树是否同构，一般都是无根树的情况。而对于同一棵树来说，选定不同的节点作为根，得到的哈希值并不相同。

但如果两棵树同构，意味着它们的重心是相同的，所以只要分别找到两棵树的重心，然后让重心作为根，再求哈希值，比较是否相同即可。

• 需要注意的是重心可能有 $2$ 个，所以需要比较 $2$ 次，只要有一次对上了就说明同构。(如果同构，则说明第一棵树的任意一个重心 $a_1$ 的哈希值一定等于第二棵树的其中一个重心的哈希值)。

例题

例1 洛谷P5043 【模板】树同构

题意

给定 $M$ 棵树，根据同构关系将它们分为等价类。

其中，$n, M \leq 50$。

题解

求出每棵树的重心，然后暴力两两对比即可。

代码

#include <bits/stdc++.h>
using namespace std;
const int maxn = 55;
const int maxm = 1e5+5;

struct Edge {
    int from, to, nxt;
} edges[maxm<<1];
int head[maxm], ecnt = 1;
void addEdge(int u, int v) {
    Edge e = {u, v, head[u]};
    head[u] = ecnt;
    edges[ecnt++] = e;
}

int sz[maxm], cur_tr;
int M;
int rt[maxn], tr_sz[maxn];
vector<int> cent[maxn];
ull h[maxm], base = rng();
ull H(ull x){
	return x*x*x*19890535+19260817;
}
ull F(ull x){
	return H(x&((1ll<<32)-1))+H(x>>32);
}

void dfs1(int u, int p) {
    sz[u] = 1;
    int mx = 0;
    for (int e = head[u]; e; e = edges[e].nxt) {
        int v = edges[e].to;
        if (v == p) continue;
        dfs1(v, u);
        sz[u] += sz[v];
        mx = max(mx, sz[v]);
    }
    int cur_sz = tr_sz[cur_tr];
    mx = max(mx, cur_sz - sz[u]);
    if (mx <= cur_sz / 2) cent[cur_tr].push_back(u);
}

vector<ull> ha[maxn];
void dfs2(int u, int p) {
    h[u] = base;
    for (int e = head[u]; e; e = edges[e].nxt) {
        int v = edges[e].to;
        if (v == p) continue;
        dfs2(v, u);
        h[u] += F(h[v]);
    }
}


int main() {
    cin >> M;

    int id = 0;
    for (int j = 1; j <= M; j++) {
        int n; cin >> n;
        tr_sz[j] = n;
        for (int i = 1; i <= n; i++) {
            int p; cin >> p;
            if (p > 0) {
                p += id;
                addEdge(p, i+id);
                addEdge(i+id, p);
            } else {
                rt[j] = i + id;
            }
        }
        id += n;
    }

    for (int j = 1; j <= M; j++) {
        cur_tr = j;
        dfs1(rt[j], 0);
        for (int c : cent[j]) {
            dfs2(c, 0);
            ha[j].push_back(h[c]);
        }
    }

    for (int tj = 1; tj <= M; tj++) {
        for (int ti = 1; ti <= tj; ti++) {
            bool ok = 0;
            for (ull h1 : ha[tj]) {
                for (ull h2 : ha[ti]) {
                    if (h1 == h2) ok = 1;
                }
            }
            if (ok) {
                cout << ti << "\n";
                break;
            }
        }
    }
}

例2 CF1252F Regular Forestation

题意

给定一棵无根树，问是否存在一个点 $u$，使得将点 $u$ 移除后，得到的所有子树两两同构？

如果存在，输出 degree 最大的这样的 $u$。

• 要求 $u$ 的degree至少为 $2$。

其中，$n \leq 4000$。

题解

由于 $n \leq 4000$，所以先定 $1$ 为根，然后：

找出所有子树的重心。
找出对于所有 $u$，除了 $u$ 子树以外的部分的重心。
然后对于每个 $u$，check它的所有子树和它以外的部分是否同构。

第一步可以用树的重心提到的 $O(n)$ 方法来找，第二步好像没有什么好方法，只能暴力了。

第三步注意一下重心可能有两个，然后拿个 map 记录一下哈希值的 count，注意到一棵子树最多贡献一次哈希值count即可。

复杂度是 $O(n^2)$。

代码

#include <bits/stdc++.h>
using namespace std;
const int maxn = 8005;

struct Edge {
    int from, to, nxt;
} edges[maxn<<1];
int head[maxn], ecnt = 1;
void addEdge(int u, int v) {
    Edge e = {u, v, head[u]};
    head[u] = ecnt;
    edges[ecnt++] = e;
}

int sz[maxn], deg[maxn], son[maxn], par[maxn];
vector<int> cent[maxn<<1];  // cent[i]: centroids of subtree i, cent[i+n]: centroids of up[i]
ull h[maxn], base = rng();
ull H(ull x){
	return x*x*x*19890535+19260817;
}
ull F(ull x){
	return H(x&((1ll<<32)-1))+H(x>>32);
}

void dfs1(int u, int p) {
    par[u] = p;
    sz[u] = 1;
    int mx = 0;
    for (int e = head[u]; e; e = edges[e].nxt) {
        int v = edges[e].to;
        if (v == p) continue;
        dfs1(v, u);
        if (sz[v] > sz[son[u]]) {
            son[u] = v;
        }
        sz[u] += sz[v];
        mx = max(mx, sz[v]);
    }
    if (mx <= sz[u] / 2) cent[u].push_back(u);
    if (cent[son[u]].size()) {
        int k = cent[son[u]][0];
        while (k != u) {
            if (sz[son[k]] <= sz[u] / 2 && sz[u] - sz[k] <= sz[u] / 2) {
                cent[u].push_back(k);
            }
            if (cent[u].size() >= 2 || sz[son[k]] > sz[u] / 2) break;  // 再往上不会更优了
            k = par[k];
        }
    }
}

vector<ull> ha[maxn];
void dfs2(int u, int p, int f) {
    h[u] = base;
    for (int e = head[u]; e; e = edges[e].nxt) {
        int v = edges[e].to;
        if (v == p || v == f) continue;
        dfs2(v, u, f);
        h[u] += F(h[v]);
    }
}

int cursz, currt;  // 当前考虑部分的sz, root (如果是 i 外面的，currt 就是 i + n)
void dfs3(int u, int p, int f) {
    sz[u] = 1;
    int mx = 0;
    for (int e = head[u]; e; e = edges[e].nxt) {
        int v = edges[e].to;
        if (v == p || v == f) continue;
        dfs3(v, u, f);
        sz[u] += sz[v];
        mx = max(mx, sz[v]);
    }
    if (mx <= cursz / 2 && cursz - sz[u] <= cursz / 2) {
        cent[currt].push_back(u);
    }
}

void dfs4(int u, int p, int f) {
    h[u] = base;
    for (int e = head[u]; e; e = edges[e].nxt) {
        int v = edges[e].to;
        if (v == p || v == f) continue;
        dfs4(v, u, f);
        h[u] += F(h[v]);
    }
}

int n;
int ans = 0;
int main() {
    fastio;
    cin >> n;
    for (int i = 1; i < n; i++) {
        int u, v; cin >> u >> v;
        addEdge(u, v); addEdge(v, u);
        deg[u]++; deg[v]++;
    }
    dfs1(1, 0);

    for (int i = 1; i <= n; i++) {
        for (int c : cent[i]) {
            dfs2(c, 0, par[i]);
            ha[i].push_back(h[c]);
        }
    }

    // 现在处理所有子树外的部分
    for (int i = 1; i <= n; i++) {
        if (deg[i] < 2) continue;
        bool ok = 1;
        map<ull, int> mp;  // hash: count
        int s = sz[son[i]];
        if (n - sz[i] != s) ok = 0;
        for (int e = head[i]; e; e = edges[e].nxt) {
            int v = edges[e].to;
            if (v == par[i]) continue;
            if (sz[v] != s) ok = 0;
            if (ha[v].size() == 2 && ha[v][0] == ha[v][1]) {
                mp[ha[v][0]]++;
            } else {
                for (ull hv : ha[v]) {
                    mp[hv]++;
                }
            }
        }
        if (!ok) continue;
        
        // 现在说明 i 可能为最佳切割点
        // 寻找 i 外面子树的信息 (如果有)
        if (par[i]) {
            cursz = n - sz[i];
            currt = i + n;
            dfs3(par[i], 0, i);
        }

        for (int c : cent[i+n]) {
            dfs4(c, 0, i);
            ha[i+n].push_back(h[c]);
        }
        if (ha[i+n].size() == 2 && ha[i+n][0] == ha[i+n][1]) {
            mp[ha[i+n][0]]++;
        } else {
            for (ull hv : ha[i+n]) mp[hv]++;
        }
        for (auto ptr : mp) {
            if (ptr.second == deg[i]) {
                ans = max(ans, deg[i]);
            }
        }
    }
    cout << (ans ? ans : -1) << "\n";
}

Contents

介绍

哈希方法

树同构的判断方式

例题

例1 洛谷P5043 【模板】树同构

例2 CF1252F Regular Forestation

参考链接