백준
백준 소스코드 [C++] 11437 LCA
Hani_Levenshtein
2021. 2. 24. 03:04
11437번: LCA
첫째 줄에 노드의 개수 N이 주어지고, 다음 N-1개 줄에는 트리 상에서 연결된 두 정점이 주어진다. 그 다음 줄에는 가장 가까운 공통 조상을 알고싶은 쌍의 개수 M이 주어지고, 다음 M개 줄에는 정
www.acmicpc.net
백준 소스코드 [C++] 11437 LCA
#include <iostream>
#include <algorithm>
#include <queue>
#include <string.h>
#include <limits.h>
#include <vector>
#include <math.h>
#include <stack>
#include <bitset>
#include <string>
#include <set>
#define all(v) v.begin(), v.end()
#define pii pair<int,int>
#define make_unique(v) v.erase(unique(v.begin(), v.end()), v.end())
typedef long long ll;
using namespace std;
int n, m;
vector<int> tree[50000];
int parent[50000];
int level[50000];
int chk[50000];
void getParentandLevel(int t) {
chk[t] = true;
for(auto a: tree[t])
if (chk[a] == false) {
parent[a] = t;
level[a] = level[t] + 1;
getParentandLevel(a);
}
return;
}
void searchAnc(int y, int x) {
while (level[y] > level[x]) y = parent[y];
while (level[y] < level[x]) x = parent[x];
while (y != x) {
y = parent[y];
x = parent[x];
}
cout << y + 1<<'\n';
return;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int u, v;
cin >> n;
while (--n) {
cin >> u >> v;
tree[u - 1].push_back(v - 1);
tree[v - 1].push_back(u - 1);
}
getParentandLevel(0);
cin >> m;
while (m--) {
cin >> u >> v;
searchAnc(--u, --v);
}
return 0;
}