LCA

Problem link: https://www.acmicpc.net/problem/11437

입력의 크기가 매우 작아서 단순한 알고리즘으로도 풀린다.

우선, 입력에 별도로 부모 자식 관계가 주어지지는 않으므로 입력을 그래프로 간주하여 받은 뒤 루트를 1번 노드로하는 BFS 트리를 생성해준다.

이 때 각 노드의 깊이를 함께 구해주도록 하자.

만약, a와 b의 LCA를 찾고자한다면, 아래의 방법을 따르면 된다.

• Case 1) a와 b의 깊이가 같다면, a와 b를 1칸 씩 부모로 옮겨가면서 만날 때까지 옮겨준다.
• Case 2) a와 b의 깊이가 다르다면(편의상 a가 더 깊다고하자), a를 b의 깊이까지 올려준 뒤에 Case 1)을 적용한다.

입력의 크기가 작아서 Case 2)에서 타고올라가는 부분을 간단하게 작성했는데, 입력이 큰 문제의 경우 아래와 같이 DP 아이디어를 함께 적용해서 풀어주어야 한다.

• PARENT[i][k]: i번 노드의 2^k번째 부모
• PARENT[i][k] = PARENT[PARENT[i][k-1]][k-1]

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

const int kMaxN = 50000;

int N;
int M;
int VISIT[kMaxN + 1];
vector<int> TREE[kMaxN + 1];

void DoBfs(const int root)
{
  queue<int> q;

  VISIT[root] = 1;
  q.emplace(root);

  while (!q.empty())
  {
    int here = q.front();
    q.pop();

    for (const auto& there : TREE[here])
    {
      if (VISIT[there] == 0)
      {
        VISIT[there] = VISIT[here] + 1;
        q.emplace(there);
      }
    }
  }
}

int FindCommonAncestor(const int a, const int b)
{
  if (VISIT[a] > VISIT[b])
  {
    return FindCommonAncestor(b, a);
  }

  int moved_a = a;
  int moved_b = b;

  // Move B till same depth with A
  if (VISIT[moved_a] != VISIT[moved_b])
  {
    while (VISIT[moved_a] != VISIT[moved_b])
    {
      for (const auto& neighbor : TREE[moved_b])
      {
        if (VISIT[neighbor] == VISIT[moved_b] - 1)
        {
          moved_b = neighbor;
          break;
        }
      }
    }
  }

  while (moved_a != moved_b)
  {
    for (const auto& neighbor : TREE[moved_a])
    {
      if (VISIT[neighbor] == VISIT[moved_a] - 1)
      {
        moved_a = neighbor;
        break;
      }
    }

    for (const auto& neighbor : TREE[moved_b])
    {
      if (VISIT[neighbor] == VISIT[moved_b] - 1)
      {
        moved_b = neighbor;
        break;
      }
    }
  }

  return moved_a;
}

int main(void)
{
  // For Faster IO
  ios_base::sync_with_stdio(false);
  cout.tie(nullptr);
  cin.tie(nullptr);

  // Read Input
  cin >> N;
  for (int i = 0; i < N - 1; ++i)
  {
    int src, dst;
    cin >> src >> dst;
    TREE[src].emplace_back(dst);
    TREE[dst].emplace_back(src);
  }

  // Build BFS Tree
  DoBfs(1);

  // Read Input
  cin >> M;
  while (M--)
  {
    int one, two;
    cin >> one >> two;

    // Solve
    cout << FindCommonAncestor(one, two) << '\n';
  }

  return 0;
}