[11438번] LCA 2

문제 출처 :

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

알고리즘 분석 :

문제 해결에 필요한 사항

1. LCA(Lowest Common Ancestor) :: http://www.crocus.co.kr/660

LCA 문제 :: https://www.acmicpc.net/problem/11437 및 LCA 2 문제는 

아래 코드의 MAX_NODE 만 수정하여 동일하게 해결할 수 있습니다.

이 문제는 LCA를 이해하였는지에 대한 질의를 하는 문제이고, 

 http://www.crocus.co.kr/660 이 링크에 모든 설명을 달아두었습니다.(같은 코드로 설명합니다.)

소스 코드 : 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123

#include <iostream> #include <cstdio> #include <vector> #include <cmath>   #define swap(a,b){int t = a; a = b; b = t;} #define MAX_NODE 100001   using namespace std;   // depth :: 노드의 깊이(레벨) // ac[x][y] :: x의 2^y번째 조상을 의미 int depth[MAX_NODE]; int ac[MAX_NODE][20];   typedef pair<int, int> pii; vector<int> graph[MAX_NODE];   int max_level;   void make_tree(int here, int parent) {     // here의 깊이는 부모노드깊이 + 1     depth[here] = depth[parent] + 1;       // here의 1번째 조상은 부모노드     ac[here][0] = parent;          // MAX_NODE에 log2를 씌어 내림을 해준다.     max_level = (int)floor(log2(MAX_NODE));       for (int i = 1; i <= max_level; i++)     {         // tmp :: here의 2^(i-1)번째 조상         /*              즉, ac[here][i] = ac[tmp][i-1]은             here의 2^i번째 조상은 tmp의 2^(i-1)번째 조상의 2^(i-1)번째 조상과 같다는 의미             예를들어 i = 3일때             here의 8번째 조상은 tmp(here의 4번째 조상)의 4번째 조상과 같다.             i =  4일때 here의 16번째 조상은 here의 8번째 조상(tmp)의 8번째와 같다.         */         int tmp = ac[here][i - 1];         ac[here][i] = ac[tmp][i - 1];     }       // dfs 알고리즘     int len = graph[here].size();     for (int i = 0; i < len; i++)     {         int there = graph[here][i];         if (there != parent)             make_tree(there, here);     } }   int main() {     int n, m;       scanf("%d", &n);       // 양방향 그래프 형성     for (int i = 1; i < n; i++)     {         int from, to;         scanf("%d %d", &from, &to);         graph[from].push_back(to);         graph[to].push_back(from);     }       // make_tree에 1,0이 들어가기때문에 0은 -1로 지정     depth[0] = -1;       // 루트 노드인 1번 노드부터 트리 형성     make_tree(1, 0);       // 쿼리문 시작     scanf("%d", &m);       while (m--)     {         int a, b;         scanf("%d %d", &a, &b);           if (depth[a] != depth[b])         {             // depth[b] >= depth[a]가 되도록 swap             if (depth[a] > depth[b])                 swap(a, b);               // b를 올려서 depth를 맞춰준다.             for (int i = max_level; i >= 0; i--)             {                 // b의 2^i번째 조상이 a의 depth보다 크거나 같으면 계속 조상을 타고간다.                 if (depth[a] <= depth[ac[b][i]])                     b = ac[b][i];             }         }           int lca = a;           // a와 b가 다르다면 현재 깊이가 같으니         // 깊이를 계속 올려 조상이 같아질 때까지 반복한다.         if (a != b)         {             for (int i = max_level; i >= 0; i--)             {                 if (ac[a][i] != ac[b][i])                 {                     a = ac[a][i];                     b = ac[b][i];                 }                 lca = ac[a][i];             }         }           printf("%d\n", lca);     }     return 0; }   //                                                       This source code Copyright belongs to Crocus //                                                        If you want to see more? click here >>

Crocus