test/aoj/GRL_5_C.test.cpp

View this file on GitHub
Last update: 2021-08-01 23:46:19+09:00
Problem: http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_5_C

Depends on

Code

#define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_5_C"

#include "../../graph/lca.hpp"
#include <iostream>
using namespace std;

int main() {
  int n; cin >> n;
  Graph<int> graph(n);
  for (int i = 0; i < n; ++i) {
    int k; cin >> k;
    for (int j = 0; j < k; ++j) {
      int c; cin >> c;
      graph[i].emplace_back(i, c);
    }
  }
  LCA<int> lca(0, graph);
  int q;
  cin >> q;
  for (int i = 0; i < q; ++i) { 
    int u, v;
    cin >> u >> v;
    cout << lca.get(u, v) << endl;
  }
}

#line 1 "test/aoj/GRL_5_C.test.cpp"
#define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_5_C"

#line 1 "graph/lca.hpp"


// @title LCA (最小共通祖先)
#line 1 "graph/template.hpp"



#include <iostream>
#include <vector>

template< typename T >
struct Edge {
  int from, to;
  T cost;
  Edge() {}
  Edge(int f, int t) : from(f), to(t), cost(1) {}
  Edge(int f, int t, T c) : from(f), to(t), cost(c) {}
  friend bool operator < (const Edge& lhs, const Edge& rhs) { return lhs.cost < rhs.cost; };
  friend bool operator > (const Edge& lhs, const Edge& rhs) { return rhs < lhs; };
  friend bool operator <= (const Edge& lhs, const Edge& rhs) { return !(lhs > rhs); };
  friend bool operator >= (const Edge& lhs, const Edge& rhs) { return !(lhs < rhs); };
};

template< typename T >
using Edges = std::vector< Edge< T > >;
template< typename T >
using Graph = std::vector< Edges< T > >;

template< typename T >
void debug(Graph<T> &g, int n = -1) {
    if (n == -1) n = g.size();
    for (int i = 0; i < n; ++i) {
        std::cerr << i  << "\t";
        for (auto &e: g[i]) {
            std::cerr << e.to << ",";
        }
        std::cerr << std::endl;
    }
}


#line 5 "graph/lca.hpp"

#include <cassert>
#include <cmath>
#line 9 "graph/lca.hpp"

using namespace std;

template< typename T >
struct LCA {
  using graph = Graph<T>;
  int root;
  // n : 頂点数
  const int n;
  const int log2_n;
  graph g;
  vector<vector<int>> parent;
  vector<int> depth;

  LCA(int root, const graph &g) : root(root), n(g.size()), log2_n(log2(n)+1), g(g), parent(log2_n, vector<int>(n)), depth(n) {
    dfs(g, root, root, 1);
    for (int k = 0; k+1 < log2_n; ++k) {
      parent.push_back(vector<int>(n, root)); // 要素数n, 値rootで初期化
      for (int v = n-1; v >= 0; --v) {
        int par = parent[k][v];
        parent[k+1][v] = parent[k][par];
      }
    }
  }
  
  /** 
   * par : 親のid
   * d : 木の深さ (1から始める)
   */ 
  void dfs(const graph& g, int from, int par, int d) {
    parent[0][from] = par;
    depth[from] = d;
    for (auto &e: g[from]) {
      if (depth[e.to] > 0) continue;
      dfs(g, e.to, from, d+1);
    }
  }

  int get(int v1, int v2) {
    // 深さが同じになるまで片方を登らせる
    if (depth[v1] < depth[v2]) swap(v1, v2);
    for (int k = 0; k < log2_n; ++k) {
      if ((depth[v1]-depth[v2]) >> k & 1) {
        v1 = parent[k][v1];
      }
    }
    if (v1 == v2) return v1;

    // 親が同じになる直前まで登らせる
    for (int k = log2_n-1; k >= 0; --k) {
      int p_v1 = parent[k][v1];
      int p_v2 = parent[k][v2];
      if (p_v1 == p_v2) continue;
      v1 = p_v1;
      v2 = p_v2;
    }
    assert(parent[0][v1] == parent[0][v2]);
    return parent[0][v1];
  }
};


#line 5 "test/aoj/GRL_5_C.test.cpp"
using namespace std;

int main() {
  int n; cin >> n;
  Graph<int> graph(n);
  for (int i = 0; i < n; ++i) {
    int k; cin >> k;
    for (int j = 0; j < k; ++j) {
      int c; cin >> c;
      graph[i].emplace_back(i, c);
    }
  }
  LCA<int> lca(0, graph);
  int q;
  cin >> q;
  for (int i = 0; i < q; ++i) { 
    int u, v;
    cin >> u >> v;
    cout << lca.get(u, v) << endl;
  }
}