白駿11437 LCA
16304 ワード
質問リンク
https://www.acmicpc.net/problem/11437
質問する
コード#コード#
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
vector<int> tree[50001];
int depth[50001];
int parent[20][50001];
void dfs(int node, int p) {
parent[0][node] = p;
depth[node] = depth[p] + 1;
for (auto nxt : tree[node]) {
if (nxt != p) {
dfs(nxt, node);
}
}
return;
}
int find_lca(int a, int b) {
int da = depth[a];
int db = depth[b];
if (da < db) {
swap(a, b);
}
da = depth[a];
db = depth[b];
int dif = da - db;
for (int i = 19; i > -1; i--) {
if (dif & (1 << i)) {
a = parent[i][a];
}
}
int LCA = a;
if (a != b) {
for (int i = 19; i > -1; i--) {
if (parent[i][a] != -1 && parent[i][a] != parent[i][b]) {
a = parent[i][a];
b = parent[i][b];
}
}
LCA = parent[0][a];
}
return LCA;
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
int n;
cin >> n;
for (int i = 0; i < n-1; i++) {
int a, b;
cin >> a >> b;
tree[a].push_back(b);
tree[b].push_back(a);
}
fill(&parent[0][0], &parent[19][50001], -1);
dfs(1, 0);
for (int i = 1; i < 20; i++) {
for (int j = 1; j <= n; j++) {
parent[i][j] = parent[i - 1][parent[i - 1][j]];
}
}
int m;
cin >> m;
for (int i = 0; i < m; i++) {
int a, b;
cin >> a >> b;
cout <<find_lca(a,b)<<'\n';
}
}
ポスト
LCAアルゴリズムは初めての接触,学習,解答である.
https://seongjuk.tistory.com/entry/BOJ-%EB%B0%B1%EC%A4%80-11437%EB%B2%88-LCA
https://www.crocus.co.kr/660#recentComments
関連ブログはよく整理されています!
見やすく、近づいてきましたが、思ったより難しかったです.
時間があるときにもう一度復習しましょう.
Reference
この問題について(白駿11437 LCA), 我々は、より多くの情報をここで見つけました https://velog.io/@bgg01578/백준-11437-LCAテキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol