Hash of Tree
(graph/tree/tree_hash.hpp)

View this file on GitHub
Last update: 2026-08-13 01:41:40+09:00
Include: #include "graph/tree/tree_hash.hpp"

Overview

m1une::tree::TreeHasher computes order-independent structural hashes of a tree. It can hash every rooted subtree, one whole rooted tree, or an unrooted tree using its one or two centers.

The implementation is iterative and uses two independent coordinates modulo $2^{61}-1$. Equal rooted trees always receive equal values when the same seed is used. Different trees can collide with very small probability, so this is suited to contest algorithms rather than cryptographic use.

The input must be a connected undirected tree built with m1une::graph::Graph<T>::add_edge. Inactive edges are ignored, and edge costs do not affect the hash.

Types

Type	Definition	Description
`TreeHashValue`	`std::array<std::uint64_t, 2>`	A comparable double hash.
`TreeHasher`	Class	Holds the seed used to generate height salts.

Methods

Method	Description	Complexity
`TreeHasher(std::uint64_t seed = ...)`	Creates a hasher. Use the same seed for comparable results.	$O(1)$
`std::uint64_t seed() const`	Returns the configured seed.	$O(1)$
`std::vector<TreeHashValue> hash_subtrees(g, root = 0) const`	Returns the hash of every subtree after rooting `g` at `root`.	$O(N)$
`TreeHashValue hash_rooted(g, root = 0) const`	Returns the hash of the whole tree rooted at `root`. For an empty graph, returns `{0, 0}`.	$O(N)$
`std::vector<TreeHashValue> hash_unrooted(g) const`	Returns the sorted hashes at the tree center or two centers. For an empty graph, returns an empty vector.	$O(N)$

Every operation uses $O(N)$ temporary memory except the constructor and seed().

Two rooted subtrees are isomorphic with high probability exactly when their TreeHashValues compare equal. Two unrooted trees are isomorphic with high probability exactly when the vectors returned by hash_unrooted compare equal.

Example

#include "graph/graph.hpp"
#include "graph/tree/tree_hash.hpp"
#include <iostream>

int main() {
    m1une::graph::Graph<int> g(5);
    g.add_edge(0, 1);
    g.add_edge(0, 2);
    g.add_edge(1, 3);
    g.add_edge(2, 4);

    m1une::tree::TreeHasher hasher;
    auto hash = hasher.hash_subtrees(g, 0);
    std::cout << (hash[1] == hash[2]) << "\n"; // 1
}

Depends on

Graph (graph/graph.hpp)

Required by

Verified with

Code

#ifndef M1UNE_TREE_TREE_HASH_HPP
#define M1UNE_TREE_TREE_HASH_HPP 1

#include <algorithm>
#include <array>
#include <cassert>
#include <cstdint>
#include <vector>

#include "../graph.hpp"

namespace m1une {
namespace tree {

using TreeHashValue = std::array<std::uint64_t, 2>;

class TreeHasher {
   private:
    static constexpr std::uint64_t mod = (std::uint64_t(1) << 61) - 1;
    std::uint64_t _seed;

    static std::uint64_t splitmix64(std::uint64_t x) {
        x += 0x9e3779b97f4a7c15ULL;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9ULL;
        x = (x ^ (x >> 27)) * 0x94d049bb133111ebULL;
        return x ^ (x >> 31);
    }

    static std::uint64_t mul_mod(std::uint64_t a, std::uint64_t b) {
        __uint128_t product = static_cast<__uint128_t>(a) * b;
        std::uint64_t result = std::uint64_t(product & mod) + std::uint64_t(product >> 61);
        if (mod <= result) result -= mod;
        return result;
    }

    static std::uint64_t add_mod(std::uint64_t a, std::uint64_t b) {
        std::uint64_t result = a + b;
        if (mod <= result) result -= mod;
        return result;
    }

    TreeHashValue salt(int height) const {
        std::uint64_t x = static_cast<std::uint64_t>(height);
        std::uint64_t first = splitmix64(_seed ^ (x + 0x243f6a8885a308d3ULL));
        std::uint64_t second = splitmix64(_seed ^ (x + 0x13198a2e03707344ULL));
        return {first % (mod - 1) + 1, second % (mod - 1) + 1};
    }

    template <class T>
    static std::vector<int> tree_centers(const m1une::graph::Graph<T>& g) {
        int n = g.size();
        if (n == 0) return {};

        std::vector<int> degree(n, 0);
        std::vector<int> queue;
        queue.reserve(n);
        long long active_arcs = 0;
        for (int v = 0; v < n; v++) {
            for (const auto& e : g[v]) {
                if (!e.alive) continue;
                degree[v]++;
                active_arcs++;
            }
            if (degree[v] <= 1) queue.push_back(v);
        }
        assert(active_arcs == 2LL * (n - 1));

        std::vector<char> removed(n, false);
        int remaining = n;
        int head = 0;
        while (2 < remaining) {
            int layer_end = int(queue.size());
            assert(head < layer_end);
            remaining -= layer_end - head;
            while (head < layer_end) {
                int v = queue[head++];
                removed[v] = true;
                for (const auto& e : g[v]) {
                    if (!e.alive || removed[e.to]) continue;
                    if (--degree[e.to] == 1) queue.push_back(e.to);
                }
            }
        }

        std::vector<int> centers;
        for (int v = 0; v < n; v++) {
            if (!removed[v]) centers.push_back(v);
        }
        assert(1 <= int(centers.size()) && int(centers.size()) <= 2);
        return centers;
    }

   public:
    explicit TreeHasher(std::uint64_t seed = 0x6a09e667f3bcc909ULL) : _seed(seed) {}

    std::uint64_t seed() const {
        return _seed;
    }

    template <class T>
    std::vector<TreeHashValue> hash_subtrees(const m1une::graph::Graph<T>& g, int root = 0) const {
        int n = g.size();
        if (n == 0) return {};
        assert(0 <= root && root < n);

        std::vector<int> parent(n, -1);
        std::vector<int> order;
        order.reserve(n);
        parent[root] = root;
        order.push_back(root);
        long long active_arcs = 0;
        for (int v = 0; v < n; v++) {
            for (const auto& e : g[v]) active_arcs += e.alive;
        }
        assert(active_arcs == 2LL * (n - 1));

        for (int i = 0; i < int(order.size()); i++) {
            int v = order[i];
            for (const auto& e : g[v]) {
                if (!e.alive || parent[e.to] != -1) continue;
                parent[e.to] = v;
                order.push_back(e.to);
            }
        }
        assert(int(order.size()) == n);

        std::vector<int> height(n, 0);
        std::vector<TreeHashValue> result(n, TreeHashValue{1, 1});
        for (int i = n - 1; i >= 0; i--) {
            int v = order[i];
            for (const auto& e : g[v]) {
                if (!e.alive || parent[e.to] != v) continue;
                height[v] = std::max(height[v], height[e.to] + 1);
            }
            TreeHashValue random = salt(height[v]);
            for (const auto& e : g[v]) {
                if (!e.alive || parent[e.to] != v) continue;
                result[v][0] = mul_mod(result[v][0], add_mod(result[e.to][0], random[0]));
                result[v][1] = mul_mod(result[v][1], add_mod(result[e.to][1], random[1]));
            }
        }
        return result;
    }

    template <class T>
    TreeHashValue hash_rooted(const m1une::graph::Graph<T>& g, int root = 0) const {
        if (g.empty()) return {0, 0};
        return hash_subtrees(g, root)[root];
    }

    template <class T>
    std::vector<TreeHashValue> hash_unrooted(const m1une::graph::Graph<T>& g) const {
        std::vector<int> centers = tree_centers(g);
        std::vector<TreeHashValue> result;
        result.reserve(centers.size());
        for (int center : centers) result.push_back(hash_rooted(g, center));
        std::sort(result.begin(), result.end());
        return result;
    }
};

}  // namespace tree
}  // namespace m1une

#endif  // M1UNE_TREE_TREE_HASH_HPP

#line 1 "graph/tree/tree_hash.hpp"



#include <algorithm>
#include <array>
#include <cassert>
#include <cstdint>
#include <vector>

#line 1 "graph/graph.hpp"



#line 6 "graph/graph.hpp"
#include <utility>
#line 8 "graph/graph.hpp"

namespace m1une {
namespace graph {

template <class T = int>
struct Edge {
    using cost_type = T;

    int from;
    int to;
    T cost;
    int id;
    bool alive;

    Edge() : from(-1), to(-1), cost(T()), id(-1), alive(true) {}
    Edge(int from_, int to_, T cost_ = T(1), int id_ = -1, bool alive_ = true)
        : from(from_), to(to_), cost(cost_), id(id_), alive(alive_) {}

    int other(int v) const {
        assert(v == from || v == to);
        return from ^ to ^ v;
    }
};

template <class T = int>
struct Graph {
    using edge_type = Edge<T>;
    using cost_type = T;

   private:
    struct EdgePositions {
        std::array<std::pair<int, int>, 2> value{};
        int size = 0;

        void push_back(std::pair<int, int> position) {
            assert(size < 2);
            value[size++] = position;
        }
    };

    int _n;
    int _edge_count;
    std::vector<std::vector<edge_type>> _g;
    std::vector<EdgePositions> _edge_positions;

   public:
    Graph() : _n(0), _edge_count(0) {}
    explicit Graph(int n) : _n(n), _edge_count(0), _g(n) {
        assert(0 <= n);
    }

    int size() const {
        return _n;
    }

    bool empty() const {
        return _n == 0;
    }

    int edge_count() const {
        return _edge_count;
    }

    int add_vertex() {
        _g.emplace_back();
        return _n++;
    }

    int add_directed_edge(int from, int to, T cost = T(1)) {
        assert(0 <= from && from < _n);
        assert(0 <= to && to < _n);
        int id = _edge_count++;
        int idx = int(_g[from].size());
        _g[from].push_back(edge_type(from, to, cost, id));
        _edge_positions.emplace_back();
        _edge_positions.back().push_back({from, idx});
        return id;
    }

    int add_edge(int u, int v, T cost = T(1)) {
        assert(0 <= u && u < _n);
        assert(0 <= v && v < _n);
        int id = _edge_count++;
        int u_idx = int(_g[u].size());
        _g[u].push_back(edge_type(u, v, cost, id));
        int v_idx = int(_g[v].size());
        _g[v].push_back(edge_type(v, u, cost, id));
        _edge_positions.emplace_back();
        _edge_positions.back().push_back({u, u_idx});
        _edge_positions.back().push_back({v, v_idx});
        return id;
    }

    void set_edge_alive(int id, bool alive) {
        assert(0 <= id && id < _edge_count);
        for (int i = 0; i < _edge_positions[id].size; ++i) {
            auto [v, idx] = _edge_positions[id].value[i];
            _g[v][idx].alive = alive;
        }
    }

    void erase_edge(int id) {
        set_edge_alive(id, false);
    }

    void revive_edge(int id) {
        set_edge_alive(id, true);
    }

    bool is_edge_alive(int id) const {
        assert(0 <= id && id < _edge_count);
        assert(_edge_positions[id].size != 0);
        auto [v, idx] = _edge_positions[id].value[0];
        return _g[v][idx].alive;
    }

    const std::vector<edge_type>& operator[](int v) const {
        assert(0 <= v && v < _n);
        return _g[v];
    }

    std::vector<edge_type>& operator[](int v) {
        assert(0 <= v && v < _n);
        return _g[v];
    }

    const std::vector<std::vector<edge_type>>& adjacency() const {
        return _g;
    }

    std::vector<std::vector<edge_type>>& adjacency() {
        return _g;
    }

    std::vector<edge_type> edges(bool include_inactive = false) const {
        std::vector<edge_type> result;
        result.reserve(_edge_count);
        std::vector<char> used(_edge_count, false);
        for (int v = 0; v < _n; v++) {
            for (const auto& e : _g[v]) {
                if (!include_inactive && !e.alive) continue;
                if (0 <= e.id && e.id < _edge_count) {
                    if (used[e.id]) continue;
                    used[e.id] = true;
                }
                result.push_back(e);
            }
        }
        return result;
    }

    Graph reversed() const {
        Graph result(_n);
        result._edge_count = _edge_count;
        result._edge_positions.assign(_edge_count, {});
        for (int v = 0; v < _n; v++) {
            for (const auto& e : _g[v]) {
                int idx = int(result._g[e.to].size());
                result._g[e.to].push_back(edge_type(e.to, e.from, e.cost, e.id, e.alive));
                if (0 <= e.id && e.id < _edge_count) result._edge_positions[e.id].push_back({e.to, idx});
            }
        }
        return result;
    }
};

}  // namespace graph
}  // namespace m1une


#line 11 "graph/tree/tree_hash.hpp"

namespace m1une {
namespace tree {

using TreeHashValue = std::array<std::uint64_t, 2>;

class TreeHasher {
   private:
    static constexpr std::uint64_t mod = (std::uint64_t(1) << 61) - 1;
    std::uint64_t _seed;

    static std::uint64_t splitmix64(std::uint64_t x) {
        x += 0x9e3779b97f4a7c15ULL;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9ULL;
        x = (x ^ (x >> 27)) * 0x94d049bb133111ebULL;
        return x ^ (x >> 31);
    }

    static std::uint64_t mul_mod(std::uint64_t a, std::uint64_t b) {
        __uint128_t product = static_cast<__uint128_t>(a) * b;
        std::uint64_t result = std::uint64_t(product & mod) + std::uint64_t(product >> 61);
        if (mod <= result) result -= mod;
        return result;
    }

    static std::uint64_t add_mod(std::uint64_t a, std::uint64_t b) {
        std::uint64_t result = a + b;
        if (mod <= result) result -= mod;
        return result;
    }

    TreeHashValue salt(int height) const {
        std::uint64_t x = static_cast<std::uint64_t>(height);
        std::uint64_t first = splitmix64(_seed ^ (x + 0x243f6a8885a308d3ULL));
        std::uint64_t second = splitmix64(_seed ^ (x + 0x13198a2e03707344ULL));
        return {first % (mod - 1) + 1, second % (mod - 1) + 1};
    }

    template <class T>
    static std::vector<int> tree_centers(const m1une::graph::Graph<T>& g) {
        int n = g.size();
        if (n == 0) return {};

        std::vector<int> degree(n, 0);
        std::vector<int> queue;
        queue.reserve(n);
        long long active_arcs = 0;
        for (int v = 0; v < n; v++) {
            for (const auto& e : g[v]) {
                if (!e.alive) continue;
                degree[v]++;
                active_arcs++;
            }
            if (degree[v] <= 1) queue.push_back(v);
        }
        assert(active_arcs == 2LL * (n - 1));

        std::vector<char> removed(n, false);
        int remaining = n;
        int head = 0;
        while (2 < remaining) {
            int layer_end = int(queue.size());
            assert(head < layer_end);
            remaining -= layer_end - head;
            while (head < layer_end) {
                int v = queue[head++];
                removed[v] = true;
                for (const auto& e : g[v]) {
                    if (!e.alive || removed[e.to]) continue;
                    if (--degree[e.to] == 1) queue.push_back(e.to);
                }
            }
        }

        std::vector<int> centers;
        for (int v = 0; v < n; v++) {
            if (!removed[v]) centers.push_back(v);
        }
        assert(1 <= int(centers.size()) && int(centers.size()) <= 2);
        return centers;
    }

   public:
    explicit TreeHasher(std::uint64_t seed = 0x6a09e667f3bcc909ULL) : _seed(seed) {}

    std::uint64_t seed() const {
        return _seed;
    }

    template <class T>
    std::vector<TreeHashValue> hash_subtrees(const m1une::graph::Graph<T>& g, int root = 0) const {
        int n = g.size();
        if (n == 0) return {};
        assert(0 <= root && root < n);

        std::vector<int> parent(n, -1);
        std::vector<int> order;
        order.reserve(n);
        parent[root] = root;
        order.push_back(root);
        long long active_arcs = 0;
        for (int v = 0; v < n; v++) {
            for (const auto& e : g[v]) active_arcs += e.alive;
        }
        assert(active_arcs == 2LL * (n - 1));

        for (int i = 0; i < int(order.size()); i++) {
            int v = order[i];
            for (const auto& e : g[v]) {
                if (!e.alive || parent[e.to] != -1) continue;
                parent[e.to] = v;
                order.push_back(e.to);
            }
        }
        assert(int(order.size()) == n);

        std::vector<int> height(n, 0);
        std::vector<TreeHashValue> result(n, TreeHashValue{1, 1});
        for (int i = n - 1; i >= 0; i--) {
            int v = order[i];
            for (const auto& e : g[v]) {
                if (!e.alive || parent[e.to] != v) continue;
                height[v] = std::max(height[v], height[e.to] + 1);
            }
            TreeHashValue random = salt(height[v]);
            for (const auto& e : g[v]) {
                if (!e.alive || parent[e.to] != v) continue;
                result[v][0] = mul_mod(result[v][0], add_mod(result[e.to][0], random[0]));
                result[v][1] = mul_mod(result[v][1], add_mod(result[e.to][1], random[1]));
            }
        }
        return result;
    }

    template <class T>
    TreeHashValue hash_rooted(const m1une::graph::Graph<T>& g, int root = 0) const {
        if (g.empty()) return {0, 0};
        return hash_subtrees(g, root)[root];
    }

    template <class T>
    std::vector<TreeHashValue> hash_unrooted(const m1une::graph::Graph<T>& g) const {
        std::vector<int> centers = tree_centers(g);
        std::vector<TreeHashValue> result;
        result.reserve(centers.size());
        for (int center : centers) result.push_back(hash_rooted(g, center));
        std::sort(result.begin(), result.end());
        return result;
    }
};

}  // namespace tree
}  // namespace m1une

m1une's library

This documentation is automatically generated by online-judge-tools/verification-helper

Hash of Tree
(graph/tree/tree_hash.hpp)

Overview

Types

Methods

Example

Depends on

Required by

Verified with

Code

Hash of Tree (graph/tree/tree_hash.hpp)

Overview

Types

Methods

Example

Depends on

Required by

Verified with

Code

Hash of Tree
(graph/tree/tree_hash.hpp)