Nyaan's Library

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

View on GitHub

:heavy_check_mark: tree/tree-hash.hpp

Depends on

Verified with

Code

#pragma once

#include "centroid.hpp"
#include "rooted-tree-hash.hpp"

template <typename G>
vector<typename RootedTreeHash<G>::Hash> tree_hash(const G& g) {
  using Hash = typename RootedTreeHash<G>::Hash;
  auto cs = centroid(g);
  if ((int)cs.size() == 1) cs.push_back(cs[0]);
  vector<Hash> hs;
  for (auto& c : cs) hs.push_back(RootedTreeHash{g, c}.hash[c]);
  sort(begin(hs), end(hs));
  return hs;
}
#line 2 "tree/tree-hash.hpp"

#line 2 "tree/centroid.hpp"

#include <utility>
#include <vector>
using namespace std;

template <typename G>
vector<int> centroid(const G &g) {
  const int N = (int)g.size();

  vector<pair<int, int> > st;
  st.emplace_back(0, -1);
  vector<int> sz(N), par(N);
  while (!st.empty()) {
    auto p = st.back();
    if (sz[p.first] == 0) {
      sz[p.first] = 1;
      for (auto &to : g[p.first])
        if (to != p.second) st.emplace_back(to, p.first);
    } else {
      for (auto &to : g[p.first])
        if (to != p.second) sz[p.first] += sz[to];
      par[p.first] = p.second;
      st.pop_back();
    }
  }

  vector<int> ret;
  int size = N;
  for (int i = 0; i < N; i++) {
    int val = N - sz[i];
    for (auto &to : g[i])
      if (to != par[i]) val = max(val, sz[to]);
    if (val < size) size = val, ret.clear();
    if (val == size) ret.emplace_back(i);
  }

  return ret;
}
#line 2 "tree/rooted-tree-hash.hpp"

#include <array>
#include <chrono>
#include <random>
#line 7 "tree/rooted-tree-hash.hpp"
using namespace std;

#line 2 "internal/internal-hash.hpp"

namespace internal {
using i64 = long long;
using u64 = unsigned long long;
using u128 = __uint128_t;

template <int BASE_NUM = 2>
struct Hash : array<u64, BASE_NUM> {
  using array<u64, BASE_NUM>::operator[];
  static constexpr int n = BASE_NUM;

  Hash() : array<u64, BASE_NUM>() {}

  static constexpr u64 md = (1ull << 61) - 1;

  constexpr static Hash set(const i64 &a) {
    Hash res;
    fill(begin(res), end(res), cast(a));
    return res;
  }
  Hash &operator+=(const Hash &r) {
    for (int i = 0; i < n; i++)
      if (((*this)[i] += r[i]) >= md) (*this)[i] -= md;
    return *this;
  }
  Hash &operator+=(const i64 &r) {
    u64 s = cast(r);
    for (int i = 0; i < n; i++)
      if (((*this)[i] += s) >= md) (*this)[i] -= md;
    return *this;
  }
  Hash &operator-=(const Hash &r) {
    for (int i = 0; i < n; i++)
      if (((*this)[i] += md - r[i]) >= md) (*this)[i] -= md;
    return *this;
  }
  Hash &operator-=(const i64 &r) {
    u64 s = cast(r);
    for (int i = 0; i < n; i++)
      if (((*this)[i] += md - s) >= md) (*this)[i] -= md;
    return *this;
  }
  Hash &operator*=(const Hash &r) {
    for (int i = 0; i < n; i++) (*this)[i] = modmul((*this)[i], r[i]);
    return *this;
  }
  Hash &operator*=(const i64 &r) {
    u64 s = cast(r);
    for (int i = 0; i < n; i++) (*this)[i] = modmul((*this)[i], s);
    return *this;
  }

  Hash operator+(const Hash &r) { return Hash(*this) += r; }
  Hash operator+(const i64 &r) { return Hash(*this) += r; }
  Hash operator-(const Hash &r) { return Hash(*this) -= r; }
  Hash operator-(const i64 &r) { return Hash(*this) -= r; }
  Hash operator*(const Hash &r) { return Hash(*this) *= r; }
  Hash operator*(const i64 &r) { return Hash(*this) *= r; }
  Hash operator-() const {
    Hash res;
    for (int i = 0; i < n; i++) res[i] = (*this)[i] == 0 ? 0 : md - (*this)[i];
    return res;
  }
  friend Hash pfma(const Hash &a, const Hash &b, const Hash &c) {
    Hash res;
    for (int i = 0; i < n; i++) res[i] = modfma(a[i], b[i], c[i]);
    return res;
  }
  friend Hash pfma(const Hash &a, const Hash &b, const i64 &c) {
    Hash res;
    u64 s = cast(c);
    for (int i = 0; i < n; i++) res[i] = modfma(a[i], b[i], s);
    return res;
  }

  Hash pow(long long e) {
    Hash a{*this}, res{Hash::set(1)};
    for (; e; a *= a, e >>= 1) {
      if (e & 1) res *= a;
    }
    return res;
  }

  static Hash get_basis() {
    static auto rand_time =
        chrono::duration_cast<chrono::nanoseconds>(
            chrono::high_resolution_clock::now().time_since_epoch())
            .count();
    static mt19937_64 rng(rand_time);
    Hash h;
    for (int i = 0; i < n; i++) {
      while (isPrimitive(h[i] = rng() % (md - 1) + 1) == false)
        ;
    }
    return h;
  }

 private:
  static u64 modpow(u64 a, u64 b) {
    u64 r = 1;
    for (a %= md; b; a = modmul(a, a), b >>= 1) r = modmul(r, a);
    return r;
  }
  static bool isPrimitive(u64 x) {
    for (auto &d : vector<u64>{2, 3, 5, 7, 11, 13, 31, 41, 61, 151, 331, 1321})
      if (modpow(x, (md - 1) / d) <= 1) return false;
    return true;
  }
  static inline constexpr u64 cast(const long long &a) {
    return a < 0 ? a + md : a;
  }
  static inline constexpr u64 modmul(const u64 &a, const u64 &b) { 
    u128 d = u128(a) * b;
    u64 ret = (u64(d) & md) + u64(d >> 61);
    return ret >= md ? ret - md : ret;
  }
  static inline constexpr u64 modfma(const u64 &a, const u64 &b, const u64 &c) {
    u128 d = u128(a) * b + c;
    u64 ret = (d >> 61) + (u64(d) & md);
    return ret >= md ? ret - md : ret;
  }
};

}  // namespace internal

/**
 * @brief ハッシュ構造体
 * @docs docs/internal/internal-hash.md
 */
#line 10 "tree/rooted-tree-hash.hpp"

template <typename G>
struct RootedTreeHash {
  using Hash = internal::Hash<1>;

  const G& g;
  int n;
  vector<Hash> hash;
  vector<int> depth;

  static vector<Hash>& xs() {
    static vector<Hash> _xs;
    return _xs;
  }

  RootedTreeHash(const G& _g, int root = 0) : g(_g), n(g.size()) {
    hash.resize(n);
    depth.resize(n, 0);
    while ((int)xs().size() <= n) xs().push_back(Hash::get_basis());
    dfs(root, -1);
  }

 private:
  int dfs(int c, int p) {
    int dep = 0;
    for (auto& d : g[c]) {
      if (d != p) dep = max(dep, dfs(d, c) + 1);
    }
    Hash x = xs()[dep], h = Hash::set(1);
    for (auto& d : g[c]) {
      if (d != p) h = h * (x + hash[d]);
    }
    hash[c] = h;
    return depth[c] = dep;
  }
};

/**
 * @brief 根付き木のハッシュ
 */
#line 5 "tree/tree-hash.hpp"

template <typename G>
vector<typename RootedTreeHash<G>::Hash> tree_hash(const G& g) {
  using Hash = typename RootedTreeHash<G>::Hash;
  auto cs = centroid(g);
  if ((int)cs.size() == 1) cs.push_back(cs[0]);
  vector<Hash> hs;
  for (auto& c : cs) hs.push_back(RootedTreeHash{g, c}.hash[c]);
  sort(begin(hs), end(hs));
  return hs;
}
Back to top page