cp-library
競技プログラミング用 C++ ライブラリ
木のハッシュ
tree/tree_hash.hpp · GitHub で見る
共通ページ
根を持たない無向木全体の形のハッシュを求めます。頂点番号と隣接リストの順序に依存せず、木同士の同型判定に使えます。
#include "lib/tree/tree_hash.hpp"
std::vector<std::vector<int>> first{ {1}, {0, 2, 3}, {1}, {1} };
std::vector<std::vector<int>> second{ {3}, {3}, {3}, {0, 1, 2} };
auto a = tree_hash(first);
auto b = tree_hash(second);
bool same = a == b; // true: 頂点番号だけ異なる星
tree_hash(graph,seed = 既定 seed) は std::array<TreeHashValue,2> を返します。木の重心が 2 個あれば、それぞれを根にした木全体のハッシュを昇順に並べます。重心が 1 個なら同じハッシュを 2 個入れます。戻り値全体を == で比較してください。大小比較・ソートや std::map のキーとしても使えます。
入力は std::vector<std::vector<int>> の無向木です。頂点数は INT_MAX 以下とし、各辺を両方向に 1 回ずつ入れ、連結・自己ループなし・多重辺なしとしてください。空の木にも対応し、2 個のゼロ値を返します。入力を変更せず、返した値は入力の寿命に依存しません。
TreeHashValue は 2 本の 61 bit ハッシュを持ちます。既定 seed は 根付き木のハッシュ と共通で、同じプロセス内では別々に構築した木同士を比較できます。値を保存して実行をまたいで比較する場合は、tree_hash(graph,12345) のように同じ seed を指定してください。
木の同型写像は重心同士を対応させるため、同型な木の戻り値は必ず一致します。異なる木がハッシュ衝突する可能性はあります。辺・頂点のラベルや重みは扱いません。根を指定して全ての部分木のハッシュを求める場合は 根付き木のハッシュ を使ってください。
子の順序のソートや再帰は使いません。
頂点数を \(n\) として、計算は \(O(n)\) 時間・追加空間です。返すハッシュは \(O(1)\) 空間で、比較は \(O(1)\) 時間です。
依存ライブラリ
コード
#ifndef TREE_HASH_HPP
#define TREE_HASH_HPP
#include "../components/tree_hash_core.hpp"
#include <utility>
inline std::array<TreeHashValue, 2> tree_hash(const std::vector<std::vector<int>> &graph,
std::uint64_t seed = tree_hash_detail::default_seed()) {
std::array<TreeHashValue, 2> result{};
if (graph.empty()) return result;
auto tree = tree_hash_detail::root_tree(graph, 0);
const int n = static_cast<int>(graph.size());
int first = 0;
for (int v = 1; v < n; ++v)
if (tree.size[v] >= n / 2 + n % 2 && tree.size[v] < tree.size[first]) first = v;
int second = tree.size[first] == n / 2 ? tree.parent[first] : -1;
if (first != 0) tree = tree_hash_detail::root_tree(graph, first);
auto hashes = tree_hash_detail::hashes(graph, tree, seed);
result[0] = hashes[first];
if (second == -1) result[1] = result[0];
else {
int height = 0;
for (int u : graph[first]) if (u != second) height = std::max(height, tree.height[u] + 1);
auto salt = tree_hash_detail::salt_at(height, seed);
TreeHashValue branch{ {1, 1} };
for (int u : graph[first]) if (u != second) tree_hash_detail::append(branch, hashes[u], salt);
salt = tree_hash_detail::salt_at(std::max(tree.height[second], height + 1), seed);
result[1] = { {1, 1} };
for (int u : graph[second]) tree_hash_detail::append(result[1], u == first ? branch : hashes[u], salt);
if (result[1] < result[0]) std::swap(result[0], result[1]);
}
return result;
}
#endif
#line 1 "tree/tree_hash.hpp"
#line 1 "components/tree_hash_core.hpp"
#line 1 "components/splitmix64.hpp"
#include <cstdint>
inline std::uint64_t splitmix64(std::uint64_t x) {
x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9ULL;
x = (x ^ (x >> 27)) * 0x94d049bb133111ebULL;
return x ^ (x >> 31);
}
class SplitMix64 {
std::uint64_t state;
public:
explicit SplitMix64(std::uint64_t seed = 0) : state(seed) {}
std::uint64_t operator()() { return splitmix64(state += 0x9e3779b97f4a7c15ULL); }
};
#line 5 "components/tree_hash_core.hpp"
#include <algorithm>
#include <array>
#include <cassert>
#include <chrono>
#include <compare>
#include <cstddef>
#line 12 "components/tree_hash_core.hpp"
#include <limits>
#include <vector>
struct TreeHashValue {
std::array<std::uint64_t, 2> value{};
auto operator<=>(const TreeHashValue &) const = default;
struct Hasher {
std::size_t operator()(const TreeHashValue &hash) const noexcept {
return splitmix64(hash.value[0] ^ splitmix64(hash.value[1]));
}
};
};
namespace tree_hash_detail {
inline constexpr std::uint64_t mod = (std::uint64_t(1) << 61) - 1;
inline std::uint64_t default_seed() {
static const std::uint64_t seed = splitmix64(std::uint64_t(std::chrono::steady_clock::now().time_since_epoch().count()) ^
std::uint64_t(reinterpret_cast<std::uintptr_t>(&mod)));
return seed;
}
inline std::uint64_t mul(std::uint64_t a, std::uint64_t b) {
__uint128_t product = __uint128_t(a) * b;
std::uint64_t value = (std::uint64_t(product) & mod) + std::uint64_t(product >> 61);
return value >= mod ? value - mod : value;
}
struct Rooting {
std::vector<int> parent, order, height, size;
};
inline Rooting root_tree(const std::vector<std::vector<int>> &graph, int root) {
assert(graph.size() <= std::size_t(std::numeric_limits<int>::max()));
const int n = static_cast<int>(graph.size());
assert(n ? 0 <= root && root < n : root == 0 || root == -1);
Rooting result;
if (!n) return result;
result.parent.assign(n, -2);
result.height.assign(n, 0);
result.size.assign(n, 1);
result.order.reserve(n);
result.parent[root] = -1;
result.order.push_back(root);
[[maybe_unused]] std::size_t edges = 0;
for (std::size_t i = 0; i < result.order.size(); ++i) {
int v = result.order[i];
edges += graph[v].size();
for (int u : graph[v]) {
assert(0 <= u && u < n && u != v);
if (u == result.parent[v]) continue;
assert(result.parent[u] == -2);
result.parent[u] = v;
result.order.push_back(u);
}
}
assert(result.order.size() == graph.size() && edges == std::size_t(n - 1) * 2);
for (auto it = result.order.rbegin(); it != result.order.rend(); ++it) {
int v = *it, p = result.parent[v];
if (p == -1) continue;
result.height[p] = std::max(result.height[p], result.height[v] + 1);
result.size[p] += result.size[v];
}
return result;
}
inline Rooting root_parents(const std::vector<int> &parent) {
assert(parent.size() <= std::size_t(std::numeric_limits<int>::max()));
const int n = static_cast<int>(parent.size());
Rooting result;
result.parent = parent;
result.height.assign(n, 0);
result.size.assign(n, 1);
result.order.reserve(n);
std::vector<int> degree(n);
int root = -1;
for (int v = 0; v < n; ++v) {
int p = parent[v];
assert(p == -1 || (0 <= p && p < n && p != v));
if (p == -1) { assert(root == -1); root = v; }
else ++degree[p];
}
assert(!n || root != -1);
for (int v = 0; v < n; ++v) if (!degree[v]) result.order.push_back(v);
for (std::size_t i = 0; i < result.order.size(); ++i) {
int v = result.order[i], p = parent[v];
if (p == -1) continue;
result.height[p] = std::max(result.height[p], result.height[v] + 1);
result.size[p] += result.size[v];
if (!--degree[p]) result.order.push_back(p);
}
assert(result.order.size() == parent.size());
std::reverse(result.order.begin(), result.order.end());
return result;
}
inline TreeHashValue salt_at(int height, std::uint64_t seed) {
SplitMix64 random(seed + std::uint64_t(height) * 2 * 0x9e3779b97f4a7c15ULL);
return { {random() % (mod - 1) + 1, random() % (mod - 1) + 1} };
}
inline void append(TreeHashValue &hash, const TreeHashValue &child, const TreeHashValue &salt) {
for (int k = 0; k < 2; ++k) {
std::uint64_t factor = salt.value[k] + child.value[k];
if (factor >= mod) factor -= mod;
hash.value[k] = mul(hash.value[k], factor);
}
}
inline std::vector<TreeHashValue> hashes(const Rooting &tree, std::uint64_t seed) {
std::vector<TreeHashValue> result(tree.parent.size(), TreeHashValue{ {1, 1} });
if (result.empty()) return result;
std::vector<TreeHashValue> salt(tree.height[tree.order[0]] + 1);
SplitMix64 random(seed);
for (auto &value : salt) value = { {random() % (mod - 1) + 1, random() % (mod - 1) + 1} };
for (auto it = tree.order.rbegin(); it + 1 != tree.order.rend(); ++it) {
int v = *it, p = tree.parent[v];
append(result[p], result[v], salt[tree.height[p]]);
}
return result;
}
inline std::vector<TreeHashValue> hashes(const std::vector<std::vector<int>> &graph, const Rooting &tree, std::uint64_t seed) {
assert(graph.size() == tree.parent.size());
return hashes(tree, seed);
}
}
#line 5 "tree/tree_hash.hpp"
#include <utility>
inline std::array<TreeHashValue, 2> tree_hash(const std::vector<std::vector<int>> &graph,
std::uint64_t seed = tree_hash_detail::default_seed()) {
std::array<TreeHashValue, 2> result{};
if (graph.empty()) return result;
auto tree = tree_hash_detail::root_tree(graph, 0);
const int n = static_cast<int>(graph.size());
int first = 0;
for (int v = 1; v < n; ++v)
if (tree.size[v] >= n / 2 + n % 2 && tree.size[v] < tree.size[first]) first = v;
int second = tree.size[first] == n / 2 ? tree.parent[first] : -1;
if (first != 0) tree = tree_hash_detail::root_tree(graph, first);
auto hashes = tree_hash_detail::hashes(graph, tree, seed);
result[0] = hashes[first];
if (second == -1) result[1] = result[0];
else {
int height = 0;
for (int u : graph[first]) if (u != second) height = std::max(height, tree.height[u] + 1);
auto salt = tree_hash_detail::salt_at(height, seed);
TreeHashValue branch{ {1, 1} };
for (int u : graph[first]) if (u != second) tree_hash_detail::append(branch, hashes[u], salt);
salt = tree_hash_detail::salt_at(std::max(tree.height[second], height + 1), seed);
result[1] = { {1, 1} };
for (int u : graph[second]) tree_hash_detail::append(result[1], u == first ? branch : hashes[u], salt);
if (result[1] < result[0]) std::swap(result[0], result[1]);
}
return result;
}