test/aoj/GRL/GRL_5_C.test.cpp

View this file on GitHub
Last update: 2023-11-11 17:58:53+09:00
Problem: https://onlinejudge.u-aizu.ac.jp/problems/GRL_5_C

Depends on

Code

#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/problems/GRL_5_C"

#include "../../../template/template.hpp"

#include "../../../graph/lca.hpp"

int main(){
  cin.tie(nullptr);
  ios::sync_with_stdio(false);
  int n;
  cin >> n;
  vvi root(n);
  rep(i, n){
    int k, c;
    cin >> k;
    rep(j, k){
      cin >> c;
      root[i].push_back(c);
    }
  }
  lca<vvi> g(root);
  int q;
  cin >> q;
  rep(i, q){
    int u,v;
    cin >> u >> v;
    cout << g.query(u, v) << "\n";
  }
}

#line 1 "test/aoj/GRL/GRL_5_C.test.cpp"
#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/problems/GRL_5_C"

#line 1 "template/template.hpp"
#include <iostream>
#include <cmath>
#include <string>
#include <vector>
#include <algorithm>
#include <tuple>
#include <cstdint>
#include <cstdio>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <deque>
#include <bitset>
#include <cctype>
#include <climits>
#include <functional>
#include <cassert>
#include <numeric>
#include <cstring>
#define rep(i, n) for(int i = 0; i < (n); i++)
#define per(i, n) for(int i = (n) - 1; i >= 0; i--)
using ll = long long;
#define vi vector<int>
#define vvi vector<vi>
#define vl vector<ll>
#define pii pair<int, int>
#define pll pair<ll, ll>
#define all(a) (a).begin(), (a).end()
#define rall(a) (a).rbegin(), (a).rend()
constexpr int mod = 1000000007;
using namespace std;
template<class T, class U>
bool chmax(T &a, const U &b){ return a < b ? (a = b, 1) : 0; }
template<class T, class U>
bool chmin(T &a, const U &b){ return a > b ? (a = b, 1) : 0; }
#line 4 "test/aoj/GRL/GRL_5_C.test.cpp"

#line 1 "graph/lca.hpp"
template <class graph>
struct lca {
  const graph &G;
  vector<vector<int>> parent;
  vector<int> dep;
  int log = 1;
  lca(const graph &G, int root = 0) : G(G){
    init(root);
  }
  void init(int root = 0){
    const int n = G.size();
    dep.assign(n, -1);
    parent.assign(1, vector<int>(n, -1));
    queue<int> que({ root });
    dep[root] = 0;
    int max_dep = 0;
    while(!que.empty()){
      const int pos = que.front();
      que.pop();
      max_dep = max(max_dep, dep[pos]);
      for(const auto &x : G[pos]){
        if(dep[x] == -1){
          dep[x] = dep[pos] + 1;
          parent[0][x] = pos;
          que.push(x);
        }
      }
    }
    while((1 << log) <= max_dep) log++;
    parent.resize(log, vector<int>(n, -1));
    for(int k = 0; k < log - 1; k++){
      for(int v = 0; v < n; v++){
        if(parent[k][v] < 0) parent[k + 1][v] = -1;
        else parent[k + 1][v] = parent[k][parent[k][v]];
      }
    }
  }
  int query(int u, int v) const{
    if(dep[u] < dep[v]) swap(u, v);
    const int sub = dep[u] - dep[v];
    for(int k = 0; k < log; k++){
      if(!(sub >> k)) break;
      if(sub >> k & 1) u = parent[k][u];
    }
    if(u == v) return u;
    for(int k = __lg(dep[u]); k >= 0; k--){
      if(parent[k][u] != parent[k][v]){
        u = parent[k][u];
        v = parent[k][v];
      }
    }
    return parent[0][u];
  }
  int dist(const int u, const int v) const{
    return dep[u] + dep[v] - dep[query(u, v)] * 2;
  }
  int jump(int u, int v, int d) const{
    const int lc = query(u, v);
    const int l = dep[u] - dep[lc];
    const int r = dep[v] - dep[lc];
    if(d < 0 || d > l + r) return -1;
    if(l < d){
      d = l + r - d;
      swap(u, v);
    }
    for(int k = 0; k < log; k++){
      if(!(d >> k)) break;
      if(d >> k & 1) u = parent[k][u];
    }
    return u;
  }
};
#line 6 "test/aoj/GRL/GRL_5_C.test.cpp"

int main(){
  cin.tie(nullptr);
  ios::sync_with_stdio(false);
  int n;
  cin >> n;
  vvi root(n);
  rep(i, n){
    int k, c;
    cin >> k;
    rep(j, k){
      cin >> c;
      root[i].push_back(c);
    }
  }
  lca<vvi> g(root);
  int q;
  cin >> q;
  rep(i, q){
    int u,v;
    cin >> u >> v;
    cout << g.query(u, v) << "\n";
  }
}