グラフ/木/最小共通祖先 ダブリング版
(test/graph/tree/lowest_common_ancestor_by_doubling.test.cpp)

• View this file on GitHub
• Last update: 2023-05-12 15:57:02+09:00
• Problem: http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_5_C

Depends on

• 辺 (include/emthrm/graph/edge.hpp)
• 最小共通祖先 (lowest common ancestor) ダブリング版 (include/emthrm/graph/tree/lowest_common_ancestor_by_doubling.hpp)

Code

/*
 * @title グラフ/木/最小共通祖先 ダブリング版
 *
 * verification-helper: PROBLEM http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_5_C
 */

#include <iostream>
#include <vector>

#include "emthrm/graph/edge.hpp"
#include "emthrm/graph/tree/lowest_common_ancestor_by_doubling.hpp"

int main() {
  int n;
  std::cin >> n;
  std::vector<std::vector<emthrm::Edge<int>>> graph(n);
  for (int i = 0; i < n; ++i) {
    int k;
    std::cin >> k;
    while (k--) {
      int c;
      std::cin >> c;
      graph[i].emplace_back(i, c, 1);
      graph[c].emplace_back(c, i, 1);
    }
  }
  emthrm::LowestCommonAncestorByDoubling<int> lowest_common_ancestor(graph);
  lowest_common_ancestor.build(0);
  int q;
  std::cin >> q;
  while (q--) {
    int u, v;
    std::cin >> u >> v;
    std::cout << lowest_common_ancestor.query(u, v) << '\n';
  }
  return 0;
}

#line 1 "test/graph/tree/lowest_common_ancestor_by_doubling.test.cpp"
/*
 * @title グラフ/木/最小共通祖先 ダブリング版
 *
 * verification-helper: PROBLEM http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_5_C
 */

#include <iostream>
#include <vector>

#line 1 "include/emthrm/graph/edge.hpp"
/**
 * @title 辺
 */

#ifndef EMTHRM_GRAPH_EDGE_HPP_
#define EMTHRM_GRAPH_EDGE_HPP_

#include <compare>

namespace emthrm {

template <typename CostType>
struct Edge {
  CostType cost;
  int src, dst;

  explicit Edge(const int src, const int dst, const CostType cost = 0)
      : cost(cost), src(src), dst(dst) {}

  auto operator<=>(const Edge& x) const = default;
};

}  // namespace emthrm

#endif  // EMTHRM_GRAPH_EDGE_HPP_
#line 1 "include/emthrm/graph/tree/lowest_common_ancestor_by_doubling.hpp"



#include <bit>
#include <cassert>
#include <utility>
#line 8 "include/emthrm/graph/tree/lowest_common_ancestor_by_doubling.hpp"

#line 1 "include/emthrm/graph/edge.hpp"
/**
 * @title 辺
 */

#ifndef EMTHRM_GRAPH_EDGE_HPP_
#define EMTHRM_GRAPH_EDGE_HPP_

#include <compare>

namespace emthrm {

template <typename CostType>
struct Edge {
  CostType cost;
  int src, dst;

  explicit Edge(const int src, const int dst, const CostType cost = 0)
      : cost(cost), src(src), dst(dst) {}

  auto operator<=>(const Edge& x) const = default;
};

}  // namespace emthrm

#endif  // EMTHRM_GRAPH_EDGE_HPP_
#line 10 "include/emthrm/graph/tree/lowest_common_ancestor_by_doubling.hpp"

namespace emthrm {

template <typename CostType>
struct LowestCommonAncestorByDoubling {
  std::vector<int> depth;
  std::vector<CostType> dist;

  explicit LowestCommonAncestorByDoubling(
      const std::vector<std::vector<Edge<CostType>>>& graph)
      : is_built(false), n(graph.size()),
        table_h(std::countr_zero(std::bit_floor(graph.size())) + 1),
        graph(graph) {
    assert(n > 0);
    depth.resize(n);
    dist.resize(n);
    parent.resize(table_h, std::vector<int>(n));
  }

  void build(const int root = 0) {
    is_built = true;
    dfs(-1, root, 0, 0);
    for (int i = 0; i + 1 < table_h; ++i) {
      for (int ver = 0; ver < n; ++ver) {
        parent[i + 1][ver] =
            (parent[i][ver] == -1 ? -1 : parent[i][parent[i][ver]]);
      }
    }
  }

  int query(int u, int v) const {
    assert(is_built);
    if (depth[u] > depth[v]) std::swap(u, v);
    for (int i = 0; i < table_h; ++i) {
      if ((depth[v] - depth[u]) >> i & 1) v = parent[i][v];
    }
    if (u == v) return u;
    for (int i = table_h - 1; i >= 0; --i) {
      if (parent[i][u] != parent[i][v]) {
        u = parent[i][u];
        v = parent[i][v];
      }
    }
    return parent.front()[u];
  }

  CostType distance(const int u, const int v) const {
    assert(is_built);
    return dist[u] + dist[v] - dist[query(u, v)] * 2;
  }

  int level_ancestor(int v, const int d) const {
    assert(is_built);
    if (depth[v] < d) return -1;
    for (int i = depth[v] - d, bit = 0; i > 0; i >>= 1, ++bit) {
      if (i & 1) v = parent[bit][v];
    }
    return v;
  }

 private:
  bool is_built;
  const int n, table_h;
  std::vector<std::vector<int>> parent;
  const std::vector<std::vector<Edge<CostType>>> graph;

  void dfs(const int par, const int ver, const int cur_depth,
           const CostType cur_dist) {
    depth[ver] = cur_depth;
    dist[ver] = cur_dist;
    parent.front()[ver] = par;
    for (const Edge<CostType>& e : graph[ver]) {
      if (e.dst != par) dfs(ver, e.dst, cur_depth + 1, cur_dist + e.cost);
    }
  }
};

}  // namespace emthrm


#line 12 "test/graph/tree/lowest_common_ancestor_by_doubling.test.cpp"

int main() {
  int n;
  std::cin >> n;
  std::vector<std::vector<emthrm::Edge<int>>> graph(n);
  for (int i = 0; i < n; ++i) {
    int k;
    std::cin >> k;
    while (k--) {
      int c;
      std::cin >> c;
      graph[i].emplace_back(i, c, 1);
      graph[c].emplace_back(c, i, 1);
    }
  }
  emthrm::LowestCommonAncestorByDoubling<int> lowest_common_ancestor(graph);
  lowest_common_ancestor.build(0);
  int q;
  std::cin >> q;
  while (q--) {
    int u, v;
    std::cin >> u >> v;
    std::cout << lowest_common_ancestor.query(u, v) << '\n';
  }
  return 0;
}

Back to top page