(11438) LCA 2

https://www.acmicpc.net/problem/11438

단계별로 풀어보기

47단계(최소 공통 조상) 3번째

 

 

 

희소 테이블을 이용해 LCA를 최적화할 수 있다.

f(x)=x의 부모 정점이라고 f를 정의하면 f(f(x))는 부모 정점의 부모 정점이고, 같은 방식으로 희소 테이블을 만들 수 있다.

이제 처음 입력된 x와 y의 트리 내 깊이를 같게 만드는 과정과 깊이를 맞춘 뒤 LCA를 구하는 과정을 희소 테이블을 이용해 O(log N)에 할 수 있다(정확히는 O(log (트리의 높이)).

테이블에서 높은 순서대로 노드 x의 2^k번째 조상을 찾아가며, 조상의 깊이보다 정점 y의 깊이가 작으면 넘어가고 아니면 조상의 값을 x에 저장한다. 이렇게 1번째 조상(부모)까지 탐색이 끝나면 x와 y의 깊이는 같아진다.

이후 다시 높은 순서대로 x와 y의 2^k번째 조상을 찾아가며 조상이 다를 때만 조상의 값을 x와 y에 저장한다. 이렇게 1번째 조상까지 탐색이 끝나면 x와 y는 최소 공통 조상의 자식이 되며 부모 정점으로 한 번 더 올라가면 정답을 구할 수 있다. 단 깊이를 맞췄을 때 x와 y가 같은 노드인 경우 x=y가 바로 최소 공통 조상이다.

 

또한 몇 가지 최적화 기법이 있는데, 희소 테이블은 목표 정점은 고정한 채 건너뛰는 높이 값을 계속 변경시키므로 v[h][n+1]보다 v[n+1][h] 형태로 선언하는 것이 어떤 정점의 점프 정보가 메모리 상에 연속적으로 배치되어 캐싱에 유리하다.

그리고 DFS에서 어떤 노드를 탐색했다면 그 조상 노드는 전부 탐색이 끝난 상태이므로 곧바로 해당 노드의 희소 테이블을 구성할 수 있다.

 

 

 

#include <iostream>
#include <vector>
#include <cmath>
using namespace std;

int main(){
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  
  int n, m;
  
  cin >> n;
  
  int h= (int)floor(log2(n))+1;
  vector adj(n+1, vector<int>()), v(n+1, vector<int> (h));
  vector<int> depth(n+1);
  
  for(int i=1;i<n;i++){
    int a, b;
    
    cin >> a >> b;
    
    adj[a].push_back(b);
    adj[b].push_back(a);
  }
  
  auto dfs= [&](auto self, int now, int prev) -> void {
    depth[now]= depth[prev]+1;
    v[now][0]= prev;
    
    for(int i=1;i<h;i++){
      v[now][i]= v[v[now][i-1]][i-1];
    }
    
    for(int next:adj[now]){
      if(next==prev)  continue;
      
      self(self, next, now);
    }
  };
  
  dfs(dfs, 1, 0);
  
  auto lca= [&](int x, int y){
    if(depth[x]<depth[y])  swap(x, y);
    
    for(int i=h-1;i>=0;i--){
      if(depth[v[x][i]]>=depth[y])  x= v[x][i];
    }
    
    if(x==y)  return x;
    
    for(int i=h-1;i>=0;i--){
      if(v[x][i]!=v[y][i]){
        x= v[x][i];
        y= v[y][i];
      }
    }
    
    return v[x][0];
  };
  
  cin >> m;
  
  while(m--){
    int a, b;
    
    cin >> a >> b;
    
    cout << lca(a, b) << "\n";
  }
  
  return 0;
}