풀이
naive한 풀이!
dfs 먼저 돌려서 각 노드마다 깊이를 구해준 뒤,
u, v 두 노드 중 더 큰 노드의 깊이를 끌어 올려준 다음에
두 노드에서 동시에 하나씩 올라가며 같은 노드에서 마주칠 때 까지 올려주면 된다.
코드
#include <stdio.h>
#include <algorithm>
#include <vector>
using namespace std;
const int n_ = 5e4 + 3;
int n, m;
int dph[n_], pnt[n_];
vector<int> gph[n_];
inline void dfs(int now, int cnt) {
dph[now] = cnt++;
for (auto nxt : gph[now]) {
if (!dph[nxt]) dfs(nxt, cnt), pnt[nxt] = now;
}
}
int main() {
int a, b, i;
scanf("%d", &n);
while (--n) {
scanf("%d %d", &a, &b);
gph[a].push_back(b);
gph[b].push_back(a);
}
dfs(1, 1);
scanf("%d", &m);
while (m--) {
scanf("%d %d", &a, &b);
if (dph[a] < dph[b]) swap(a, b);
while (dph[a] != dph[b]) a = pnt[a];
while (a != b) a = pnt[a], b = pnt[b];
printf("%d\n", a);
}
return 0;
}
아무말
백준, 백준 온라인 저지, BOJ, Baekjoon Online Judge, C, C++, 씨, 씨쁠쁠, JAVA, algorithm, 자바, 알고리즘, 자료구조, 문제, 문제 풀이, 풀이