얃얕은얏얓이얒얗
LCA2 본문
이 문제는 쉬움
https://www.acmicpc.net/problem/11438
못풀면 멍청한 사람임
못풀면 공부하고 오세요
코드는 드릴게
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 | #include <iostream> #include <vector> #include <cmath> #define swap(a,b){int t = a; a = b; b = t;} #define maxnode 100002 // 최대 노드개수입니다 using namespace std; int depth[maxnode]; // 노드의 위치(깊이)를 저장합니다. int ac[maxnode][20]; // 노드의 조상들을 저장합니다. vector <int> v[maxnode]; // 노드 쌍을 받습니다. int max_lv = (int)floor(log2(maxnode)); int a, b; // 트리를 만드는 함수입니다. void getTree(int now, int father) { // 자식은 아빠보다 아래 레벨에 있습니다 depth[now] = depth[father] + 1; // 현재의 첫 조상(2^0)은 아빠 ac[now][0] = father; // 이해하기 쉽게 나누어서 적어둡니다 // 깊이 1부터 최대 깊이 까지 돌립니다 // 이 때 현재의 첫 조상부터 조상의 조상들을 세팅해줍니다. for (int i = 1; i <= max_lv; i++) { int temp = ac[now][i - 1]; ac[now][i] = ac[temp][i - 1]; } // dfs로 들어갑니다. // 이 과정을 반복하며 자식들이 root에서 붙어가며 늘어납니다 int l = v[now].size(); for (int i = 0; i < l; i++) { int k = v[now][i]; if (k != father) getTree(k, now); } } int main() { cin.tie(NULL); ios_base::sync_with_stdio(0); int N; cin >> N; // 양방향 그래프로 만들어 줍니다. for (int i = 0; i < N-1; i++) { cin >> a >> b; v[a].push_back(b); v[b].push_back(a); } // 루트노드의 부모는 없습니다 // 패드립이 아닙니다 depth[0] = -1; // 트리를 만들고 getTree(1, 0); int M; cin >> M; // 조건을 찾아 답을 내줍시다 while (M--) { cin >> a >> b; // 글을 보고 오셨을것이라 믿고 설명합니다 // 여기서는 깊이를 비교합니다. // 깊이가 같을때까지 깊은곳에서 낮은곳으로 올려주고 // 그 후 두개 다 하나씩 올려가며 조상을 비교합니다 if (depth[a] != depth[b]) { // 비교가 편하게 스왑을 해주는 겁니다 if (depth[a] > depth[b]) swap(a, b); // 조상을 높은 차수부터 내려오면서 비교해줍니다. for (int i = max_lv; i >= 0; i--) { if (depth[a] <= depth[ac[b][i]]) b = ac[b][i]; } } int lca = a; // 같지 않다면 같을 때 까지 두들겨 패줍니다 if (a != b) { for (int i = max_lv; i >= 0; i--) { if (ac[a][i] != ac[b][i]) { a = ac[a][i]; b = ac[b][i]; } lca = ac[a][i]; } } cout << lca << '\n'; } return 0; } | cs |