木ハッシュ(Tree Hash)
(tree/tree_hash.cpp)

• View this file on GitHub
• Last update: 2026-03-12 19:34:31+09:00

説明

根付き木の各部分木を同型性で分類する。 各頂点 v について、その部分木の同型類 id を返す。

できること

• TreeHash th(n) n 頂点の木を作る
• void add_edge(int u, int v) 無向辺を追加する
• vector<int> build(int root = 0) root を根として部分木 id を構築して返す
• int th[v] 頂点 v の部分木 id を返す
• int kinds() 異なる部分木の個数を返す

使い方

辺をすべて追加してから build(root) を呼ぶ。 返る id は同じ build の中でのみ意味を持ち、id[v] == id[u] のときに限って v と u の部分木は同型である。

TreeHash th(n);
for (auto [u, v] : edges) th.add_edge(u, v);
auto id = th.build(0);

実装上の補足

• 子部分木の id をソートして辞書化することで canonical id を付ける
• 計算量はおおむね $O\left(\sum_v \deg(v)\log \deg(v)\right)$

Verified with

• test/yosupo_rooted_tree_isomorphism_classification_tree_hash.test.cpp

Code

struct TreeHash {
    int n;
    vector<vector<int>> g;
    vector<int> parent, order, hash_id;
    int kind_count;

    explicit TreeHash(int n)
        : n(n), g(n), parent(n, -1), hash_id(n, -1), kind_count(0) {}

    void add_edge(int u, int v) {
        g[u].push_back(v);
        g[v].push_back(u);
    }

    vector<int> build(int root = 0) {
        order.clear();
        order.reserve(n);
        parent.assign(n, -1);
        vector<int> st(1, root);
        parent[root] = root;
        while (!st.empty()) {
            int v = st.back();
            st.pop_back();
            order.push_back(v);
            for (int to : g[v]) {
                if (to == parent[v]) continue;
                parent[to] = v;
                st.push_back(to);
            }
        }

        map<vector<int>, int> ids;
        for (int i = n - 1; i >= 0; --i) {
            int v = order[i];
            vector<int> ch;
            ch.reserve(g[v].size() - (v != root));
            for (int to : g[v]) {
                if (to == parent[v]) continue;
                ch.push_back(hash_id[to]);
            }
            sort(ch.begin(), ch.end());
            auto [it, inserted] = ids.emplace(ch, (int)ids.size());
            hash_id[v] = it->second;
        }
        kind_count = ids.size();
        return hash_id;
    }

    int operator[](int v) const {
        return hash_id[v];
    }

    int kinds() const {
        return kind_count;
    }
};

/**
 * @brief 木ハッシュ(Tree Hash)
 */

#line 1 "tree/tree_hash.cpp"
struct TreeHash {
    int n;
    vector<vector<int>> g;
    vector<int> parent, order, hash_id;
    int kind_count;

    explicit TreeHash(int n)
        : n(n), g(n), parent(n, -1), hash_id(n, -1), kind_count(0) {}

    void add_edge(int u, int v) {
        g[u].push_back(v);
        g[v].push_back(u);
    }

    vector<int> build(int root = 0) {
        order.clear();
        order.reserve(n);
        parent.assign(n, -1);
        vector<int> st(1, root);
        parent[root] = root;
        while (!st.empty()) {
            int v = st.back();
            st.pop_back();
            order.push_back(v);
            for (int to : g[v]) {
                if (to == parent[v]) continue;
                parent[to] = v;
                st.push_back(to);
            }
        }

        map<vector<int>, int> ids;
        for (int i = n - 1; i >= 0; --i) {
            int v = order[i];
            vector<int> ch;
            ch.reserve(g[v].size() - (v != root));
            for (int to : g[v]) {
                if (to == parent[v]) continue;
                ch.push_back(hash_id[to]);
            }
            sort(ch.begin(), ch.end());
            auto [it, inserted] = ids.emplace(ch, (int)ids.size());
            hash_id[v] = it->second;
        }
        kind_count = ids.size();
        return hash_id;
    }

    int operator[](int v) const {
        return hash_id[v];
    }

    int kinds() const {
        return kind_count;
    }
};

/**
 * @brief 木ハッシュ(Tree Hash)
 */

Back to top page