트리의 임의의 두 노드 간 최소 공통 조상을 얻는 알고리즘

공통 조상을 $2^i$ 만큼 건너 뛴 배열을 통해 $O(logN)$ 시간 복잡도로 탐색 가능하다.

알고리즘

필수 변수 및 함수

const int MAXN = 40'000;

int N, M; // Node 수와 Query 수
vector<int> edges[MAXN + 3]; // Node 별 연결된 간선 정보 저장

int visited[MAXN + 3];  // 첫번째 부모 갱신을 위한 traverse 시
												// 부모를 다시 탐색하지 않기 위해 사용

int lca_parent[20][MAXN + 3]; // 조상 정보를 관리할 2차원 배열. [2^i 만큼 건너뛴 조상][Node index]
int level[MAXN + 3]; // Node 별 level 저장

void traverse(int p); // 첫번째 부모를 갱신하기 위한 traverse()

void make_lca();

int search(int a, int b); // a, b 두 노드 간 탐색 함수

1. traverse(root);를 통해 parent[v] 와 level[v] 를 갱신한다.

   parent[0][v] 처럼 index ‘0’을 바로 연결된 부모로 둔다면 부모까지의 간선 개수를 $2^i$ 로 계산할 수 있어 편리하다.

   이 경우 parent[0][root] = 0 으로 할당하면 이후 DP 방식으로 조상을 탐색할 때에 건너뛴 차이 만큼에 조상이 존재하지 않으면 0으로 할당돼 편리하다.

   void traverse(int n) {
   	visited[n] = true;
   
   	for (auto v : edges[n]) {
   		if (visited[v])
   			continue;
   
   		lca_parent[0][v] = n;
   		level[v] = level[n] + 1;
   
   		traverse(v);
   	}
   }
   

2. DP를 통해 Node마다 $2^i$ 번째 조상을 기록하는 배열을 갱신한다.

   void make_lca() {
   	for (int i = 1; i < 18; ++i) {
   		for (int j = 1; j <= N; ++j) {
   			int p = lca_parent[i - 1][j];
   			lca_parent[i][j] = lca_parent[i - 1][p];
   			// edge에 가중치가 있을 경우, distance 배열도 아래와 같이 갱신 가능하다.
   			// lca_dist[i][j] = lca_dist[i - 1][j] + lca_dist[i - 1][p];
   		}
   	}
   }
   

3. LCA search 과정

   1. 두 노드 a, b가 동일 level이 되도록 level이 더 큰 노드를 level이 작은 노드와 같아지도록 갱신한다.

      if (level[a] < level[b])
      	swap(a, b);
      
      // a에 대해 level 낮추기
      int bit = level[a] - level[b];
      for (int i = 0; bit; ++i) {
      	if ((bit & (1 << i)) == 0)
      		continue;
      
      	// 만약 거리 계산이 필요하다면 아래처럼 이동하는 거리를 누적한다.
      	// 	result += lca_dist[i][a];
      	
      	a = lca_parent[i][a];
      	
      	bit -= (1 << i);
      }
      

   2. level이 동일한 상태에서 $2^i$ 개 만큼 부모까지의 거리를 건너뛰면서 탐색하며 공통 부모를 찾는다.

      // 위의 3.a. 과정에서 LCA가 한번에 발견되었다면
      if (a == b)
      	return a;
      
      // 최소 공통 조상이 나올 때까지 2^i씩 건너뛰며 탐색
      while (lca_parent[0][a] != lca_parent[0][b]) {
      	// 공통된 부모가 나올 때까지 2배씩 건너 뛰기
      	int i = 1;
      	while (lca_parent[i][a] != lca_parent[i][b]) {
      		++i;
      	}
      
      	// 거리 계산이 필요할 경우 누산
      	//result += lca_dist[i - 1][a] + lca_dist[i - 1][b];
      
      	// 발견된 공통 부모 '하나 이전 부모 까지 a, b 갱신'
      	// lca_parent[i][a] == lca_parent[i][b]이지만, '최소' 공통 조상이 아닐 수 있다.
      	a = lca_parent[i - 1][a];
      	b = lca_parent[i - 1][b];
      }
      
      return lca_parent[0][a];
      

문제 및 풀이

정점들의 거리 (https://www.acmicpc.net/problem/1761)

트리의 두 정점 간의 거리 탐색이 $M$번(최대 1만)으로 많기 때문에, 한 번의 탐색은 $logN$ 번에 끝내야 한다. LCA가 필요하다.

특이점

• 답을 1만 개 출력할 때 cout으로 각각 출력하면 속도가 288ms 정도 나왔다. 이를 ans로 묶어서 한 번에 출력하니 28ms가 되었다. cout.tie(nullptr); 코드는 출력을 더 빠르게 해주는 것과는 무관한 듯하다.
• [Code]

도로 네트워크 (https://www.acmicpc.net/problem/3176)

놓친 부분 복기

1. level 배열이 필요한데, traverse 과정에서 눈치채고 미리 선언 못했다! traverse에서 필요한 변수는 parent[][], level이다.
2. search 부분의 첫번째 탐색 과정인 level을 맞춰주는 부분에서 d = parent[i][d]; 로직이 잘 이해가 안되었다. ex) 1101이면, 전체 13칸을 건너 뛰며 가기 위해서 각 비트의 수만큼 건너뛰고 부모로 변경된 다음 거기서부터 또 다음 비트의 수만큼 건너뛰어야 하는 것이다. 그렇지 않으면 제자리에서 1, 4, 8번째 부모만 참조하는거라 13까지 닿을 수 없다.
3. INT_MAX는 climits 헤더에 있다.