compro_library

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

View the Project on GitHub siro53/compro_library

:heavy_check_mark: 木ハッシュ
(graph/tree/tree-hash.hpp)

Depends on

Verified with

Code

#pragma once

#include "../../random/rng.hpp"
#include "diameter.hpp"

template <typename Cost = int> class TreeHash {
  public:
    explicit TreeHash(int n) : G(n) {
        RNG64 rng;
        for(int i = 0; i < n; i++) rnd.push_back(rng.randint(1, mod - 1));
    }
    explicit TreeHash(const Graph<Cost> &g) : G(g) {
        RNG64 rng;
        for(int i = 0; i < (int)G.size(); i++)
            rnd.push_back(rng.randint(1, mod - 1));
    }
    inline void add_edge(int from, int to, Cost cost = 1) {
        G.add_undirected_edge(from, to, cost);
    }
    unsigned long long get_hash() {
        auto [_, path] = get_diameter(G);
        int len = (int)path.size();
        std::vector<int> cent;
        if(len & 1) {
            cent = {path[len / 2]};
        } else {
            cent = {path[len / 2], path[len / 2 - 1]};
        }
        unsigned long long res = std::numeric_limits<unsigned long long>::max();
        for(const int &root : cent) {
            std::vector<unsigned long long> hashed(G.size(), 1);
            hash_dfs(root, -1, 0, hashed);
            res = std::min(res, hashed[root]);
        }
        return res;
    }

  private:
    Graph<Cost> G;
    static constexpr unsigned long long mod = (1ULL << 61) - 1;
    static inline std::vector<unsigned long long> rnd;

    inline unsigned long long add(unsigned long long a, unsigned long long b) {
        if((a += b) >= mod) a -= mod;
        return a;
    }
    inline unsigned long long mul(unsigned long long a, unsigned long long b) {
        __uint128_t t = a;
        t *= b;
        unsigned long long na = t >> 61;
        unsigned long long nb = t & mod;
        if((na += nb) >= mod) na -= mod;
        return na;
    }
    unsigned long long hash_dfs(int v, int p, int d,
                                std::vector<unsigned long long> &res) {
        for(const auto &e : G[v]) {
            if(e.to != p) {
                res[v] = mul(res[v], hash_dfs(e.to, v, d + 1, res));
            }
        }
        return res[v] = add(res[v], rnd[d]);
    }
};
#line 2 "graph/tree/tree-hash.hpp"

#line 2 "random/rng.hpp"

#include <chrono>
#include <random>

class RNG32 {
  public:
    RNG32() : mt(std::chrono::steady_clock::now().time_since_epoch().count()) {}
    // [l, r)
    int randint(int l, int r) {
        std::uniform_int_distribution<int> dist(l, r - 1);
        return dist(mt);
    }
    int randint(int r) { return randint(0, r); }

  private:
    std::mt19937 mt;
};

class RNG64 {
  public:
    RNG64() : mt(std::chrono::steady_clock::now().time_since_epoch().count()) {}
    // [l, r)
    long long randint(long long l, long long r) {
        std::uniform_int_distribution<long long> dist(l, r - 1);
        return dist(mt);
    }
    long long randint(long long r) { return randint(0, r); }

  private:
    std::mt19937_64 mt;
};

class RNG_0_1 {
  public:
    RNG_0_1() : mt(std::chrono::steady_clock::now().time_since_epoch().count()) {}

    // [0.0, 1.0)
    double rand() {
      auto bits = mt() >> 11;
      return (double)bits / denomitor;
    }

    auto operator()() { return rand(); }

  private:
    std::mt19937_64 mt;
    const double denomitor = 1LL << 53;
};
#line 2 "graph/tree/diameter.hpp"

#include <algorithm>
#include <utility>
#include <vector>

#line 2 "graph/graph_template.hpp"

#include <cassert>
#line 5 "graph/graph_template.hpp"

template <typename Cost = int> struct Edge {
    int from, to;
    Cost cost;
    int id;
    Edge() = default;
    explicit Edge(int from, int to, Cost cost = 1, int id = -1)
        : from(from), to(to), cost(cost), id(id) {}
    operator int() const { return to; }
};

template <typename Cost = int> class Graph {
  public:
    Graph() = default;
    explicit Graph(int N) : N(N), M(0), G(N) {}

    inline void add_directed_edge(int from, int to, Cost cost = 1) {
        assert(0 <= from && from < N);
        assert(0 <= to && to < N);
        G[from].emplace_back(from, to, cost, M++);
    }

    inline void add_undirected_edge(int from, int to, Cost cost = 1) {
        assert(0 <= from && from < N);
        assert(0 <= to && to < N);
        G[from].emplace_back(from, to, cost, M);
        G[to].emplace_back(to, from, cost, M++);
    }

    inline size_t size() const { return G.size(); }
    inline std::vector<Edge<Cost>> &operator[](const int &i) { return G[i]; }
    inline const std::vector<Edge<Cost>> &operator[](const int &i) const {
        return G[i];
    }

  protected:
    int N, M;
    std::vector<std::vector<Edge<Cost>>> G;
};

template <class Cost = int> using Edges = std::vector<Edge<Cost>>;
#line 8 "graph/tree/diameter.hpp"

template <typename Cost = int>
std::pair<Cost, std::vector<int>> get_diameter(const Graph<Cost> &G) {
    std::vector<Cost> depth(G.size());
    std::vector<int> par(G.size(), -1);
    auto dfs = [&](auto &&self, int u, int p, Cost d) -> void {
        depth[u] = d;
        par[u] = p;
        for(const auto &e : G[u]) {
            if(e.to == p) continue;
            self(self, e.to, u, d + e.cost);
        }
    };
    dfs(dfs, 0, -1, 0);
    int from = std::max_element(depth.begin(), depth.end()) - depth.begin();
    dfs(dfs, from, -1, 0);
    int to = std::max_element(depth.begin(), depth.end()) - depth.begin();
    std::vector<int> path = {to};
    while(1) {
        int nxt = par[path.back()];
        if(nxt == -1) break;
        path.push_back(nxt);
    }
    return std::make_pair(depth[to], path);
}
#line 5 "graph/tree/tree-hash.hpp"

template <typename Cost = int> class TreeHash {
  public:
    explicit TreeHash(int n) : G(n) {
        RNG64 rng;
        for(int i = 0; i < n; i++) rnd.push_back(rng.randint(1, mod - 1));
    }
    explicit TreeHash(const Graph<Cost> &g) : G(g) {
        RNG64 rng;
        for(int i = 0; i < (int)G.size(); i++)
            rnd.push_back(rng.randint(1, mod - 1));
    }
    inline void add_edge(int from, int to, Cost cost = 1) {
        G.add_undirected_edge(from, to, cost);
    }
    unsigned long long get_hash() {
        auto [_, path] = get_diameter(G);
        int len = (int)path.size();
        std::vector<int> cent;
        if(len & 1) {
            cent = {path[len / 2]};
        } else {
            cent = {path[len / 2], path[len / 2 - 1]};
        }
        unsigned long long res = std::numeric_limits<unsigned long long>::max();
        for(const int &root : cent) {
            std::vector<unsigned long long> hashed(G.size(), 1);
            hash_dfs(root, -1, 0, hashed);
            res = std::min(res, hashed[root]);
        }
        return res;
    }

  private:
    Graph<Cost> G;
    static constexpr unsigned long long mod = (1ULL << 61) - 1;
    static inline std::vector<unsigned long long> rnd;

    inline unsigned long long add(unsigned long long a, unsigned long long b) {
        if((a += b) >= mod) a -= mod;
        return a;
    }
    inline unsigned long long mul(unsigned long long a, unsigned long long b) {
        __uint128_t t = a;
        t *= b;
        unsigned long long na = t >> 61;
        unsigned long long nb = t & mod;
        if((na += nb) >= mod) na -= mod;
        return na;
    }
    unsigned long long hash_dfs(int v, int p, int d,
                                std::vector<unsigned long long> &res) {
        for(const auto &e : G[v]) {
            if(e.to != p) {
                res[v] = mul(res[v], hash_dfs(e.to, v, d + 1, res));
            }
        }
        return res[v] = add(res[v], rnd[d]);
    }
};
Back to top page