Test/Graph/Tree/LowestCommonAncestor.test.cpp

• View this file on GitHub
• Last update: 2025-06-14 20:53:47+09:00
• Problem: https://onlinejudge.u-aizu.ac.jp/courses/library/5/GRL/5/GRL_5_C

Depends on

• Library/Graph/Graph.hpp
• Library/Graph/Normal/BFS.hpp
• Library/Graph/Tree/LowestCommonAncestor.hpp

Code

#define PROBLEM \
  "https://onlinejudge.u-aizu.ac.jp/courses/library/5/GRL/5/GRL_5_C"

#include "./../../../Library/Graph/Tree/LowestCommonAncestor.hpp"


#include <iostream>


#include "./../../../Library/Graph/Graph.hpp"


using ll = long long;
using std::cin;
using std::cout;
constexpr char endl = '\n';

signed main() {
  ll n;
  cin >> n;
  mtd::Graph tree(n);
  for (int f = 0; f < n; ++f) {
    ll k;
    cin >> k;
    for (int _ = 0; _ < k; ++_) {
      int t;
      cin >> t;
      tree.addEdge(f, t);
    }
  }

  auto lca = mtd::LowestCommonAncestor(tree, 0);

  int q;
  cin >> q;
  for (int _ = 0; _ < q; ++_) {
    int u, v;
    cin >> u >> v;
    cout << lca.lca(u, v) << endl;
  }
}

#line 1 "Test/Graph/Tree/LowestCommonAncestor.test.cpp"
#define PROBLEM \
  "https://onlinejudge.u-aizu.ac.jp/courses/library/5/GRL/5/GRL_5_C"

#line 2 "Library/Graph/Tree/LowestCommonAncestor.hpp"

#include <cmath>

#include <concepts>

#include <vector>


#line 2 "Library/Graph/Graph.hpp"
#include <deque>

#include <iostream>

#include <ranges>

#include <tuple>

#line 7 "Library/Graph/Graph.hpp"

namespace mtd {
  template <class Node = long long, class Cost = long long>
  class Graph {
    using Edge = std::pair<Node, Cost>;
    using Edges = std::vector<Edge>;

    const int m_n;
    std::vector<Edges> m_graph;

  public:
    Graph(int n) : m_n(n), m_graph(n) {}
    Graph(const std::vector<Edges>& edges)
        : m_n(edges.size()), m_graph(edges) {}
    Graph(int n, const std::vector<std::tuple<Node, Node>>& edges,
          bool is_arc = false, bool is_index1 = true)
        : Graph<Node, Cost>(n) {
      for (auto [u, v] : edges) {
        u -= is_index1;
        v -= is_index1;
        if (is_arc) {
          addArc(u, v);
        } else {
          addEdge(u, v);
        }
      }
    }
    Graph(int n, const std::vector<std::tuple<Node, Node, Cost>>& edges,
          bool is_arc = false, bool is_index1 = true)
        : Graph<Node, Cost>(n) {
      for (auto [u, v, c] : edges) {
        u -= is_index1;
        v -= is_index1;
        if (is_arc) {
          addArc(u, v, c);
        } else {
          addEdge(u, v, c);
        }
      }
    }

    auto addEdge(const Node& f, const Node& t, const Cost& c = 1) {
      addArc(f, t, c);
      addArc(t, f, c);
    }
    auto addArc(const Node& f, const Node& t, const Cost& c = 1) {
      m_graph[f].emplace_back(t, c);
    }
    auto getEdges(const Node& from) const {
      class EdgesRange {
        const typename Edges::const_iterator b, e;

      public:
        EdgesRange(const Edges& edges) : b(edges.begin()), e(edges.end()) {}
        auto begin() const { return b; }
        auto end() const { return e; }
      };
      return EdgesRange(m_graph[from]);
    }
    auto getEdges() const {
      std::deque<std::tuple<Node, Node, Cost>> edges;
      for (Node from : std::views::iota(0, m_n)) {
        for (const auto& [to, c] : getEdges(from)) {
          edges.emplace_back(from, to, c);
        }
      }
      return edges;
    }
    auto getEdgesExcludeCost() const {
      std::deque<std::pair<Node, Node>> edges;
      for (Node from : std::views::iota(0, m_n)) {
        for (const auto& [to, _] : getEdges(from)) {
          edges.emplace_back(from, to);
        }
      }
      return edges;
    }
    auto reverse() const {
      auto rev = Graph<Node, Cost>(m_n);
      for (const auto& [from, to, c] : getEdges()) { rev.addArc(to, from, c); }
      return rev;
    }
    auto size() const { return m_n; };
    auto debug(bool directed = false) const {
      for (const auto& [f, t, c] : getEdges()) {
        if (f < t || directed) {
          std::cout << f << " -> " << t << ": " << c << std::endl;
        }
      }
    }
  };
}  // namespace mtd

#line 2 "Library/Graph/Normal/BFS.hpp"

#line 4 "Library/Graph/Normal/BFS.hpp"
#include <queue>

#line 6 "Library/Graph/Normal/BFS.hpp"

#line 8 "Library/Graph/Normal/BFS.hpp"

namespace mtd {
  template <class Node, class Cost, class Lambda,
            std::convertible_to<Node> _Node>
  auto bfs(const Graph<Node, Cost>& graph, const _Node& root,
           const Lambda& lambda) {
    auto n = graph.size();
    std::vector<bool> used(n);
    used[root] = true;
    std::queue<Node> q;
    q.emplace(root);
    while (!q.empty()) {
      auto from = q.front();
      q.pop();
      for (const auto& [to, cost] : graph.getEdges(from)) {
        if (used[to]) { continue; }
        q.emplace(to);
        used[to] = true;
        lambda(from, to, cost);
      }
    }
  }
}  // namespace mtd

#line 9 "Library/Graph/Tree/LowestCommonAncestor.hpp"

namespace mtd {
  template <class Node, class Cost>
  class LowestCommonAncestor {
    const std::vector<std::vector<Node>> m_parent;
    const std::vector<Node> m_depth;

    static inline auto constructParent(const Graph<Node, Cost>& tree,
                                       const Node& root) {
      auto n = tree.size();
      auto size = static_cast<int>(std::log2(n) + 1);
      std::vector<std::vector<Node>> parent(n, std::vector<Node>(size, root));
      bfs(tree, root, [&](const Node& from, const Node& to, const Cost& _) {
        parent[to][0] = from;
      });
      for (int p2 = 1; p2 < size; ++p2)
        for (int f = 0; f < n; ++f) {
          parent[f][p2] = parent[parent[f][p2 - 1]][p2 - 1];
        }
      return parent;
    }
    static inline auto constructDepth(const Graph<Node, Cost>& tree,
                                      const Node& root) {
      auto n = tree.size();
      std::vector<Node> depth(n);
      bfs(tree, root, [&](const Node& from, const Node& to, const Cost& _) {
        depth[to] = depth[from] + 1;
      });
      return depth;
    }

  public:
    template <std::convertible_to<Node> _Node>
    LowestCommonAncestor(const Graph<Node, Cost>& tree, const _Node& root)
        : m_parent(constructParent(tree, root)),
          m_depth(constructDepth(tree, root)) {}

    auto lca(Node l, Node r) const {
      int size = m_parent[0].size();
      if (m_depth[l] < m_depth[r]) { std::swap(l, r); }
      for (int k = 0; k < size; ++k) {
        if (((m_depth[l] - m_depth[r]) >> k) & 1) { l = m_parent[l][k]; }
      }
      if (l == r) { return l; }
      for (int k = size - 1; k >= 0; k--) {
        if (m_parent[l][k] != m_parent[r][k]) {
          l = m_parent[l][k];
          r = m_parent[r][k];
        }
      }
      return m_parent[l][0];
    }
  };
}  // namespace mtd

#line 5 "Test/Graph/Tree/LowestCommonAncestor.test.cpp"

#line 7 "Test/Graph/Tree/LowestCommonAncestor.test.cpp"

#line 9 "Test/Graph/Tree/LowestCommonAncestor.test.cpp"

using ll = long long;
using std::cin;
using std::cout;
constexpr char endl = '\n';

signed main() {
  ll n;
  cin >> n;
  mtd::Graph tree(n);
  for (int f = 0; f < n; ++f) {
    ll k;
    cin >> k;
    for (int _ = 0; _ < k; ++_) {
      int t;
      cin >> t;
      tree.addEdge(f, t);
    }
  }

  auto lca = mtd::LowestCommonAncestor(tree, 0);

  int q;
  cin >> q;
  for (int _ = 0; _ < q; ++_) {
    int u, v;
    cin >> u >> v;
    cout << lca.lca(u, v) << endl;
  }
}

Back to top page