# 11437

3개의 포스트

[백준 C++] 11437 LCA

문제 N(2 ≤ N ≤ 50,000)개의 정점으로 이루어진 트리가 주어진다. 트리의 각 정점은 1번부터 N번까지 번호가 매겨져 있으며, 루트는 1번이다. 두 노드의 쌍 M(1 ≤ M ≤ 10,000)개가 주어졌을 때, 두 노드의 가장 가까운 공통 조상이 몇 번인지 출

2023년 1월 15일
·
0개의 댓글
·
post-thumbnail

LCA

입력의 크기가 매우 작아서 단순한 알고리즘으로도 풀린다.우선, 입력에 별도로 부모 자식 관계가 주어지지는 않으므로 입력을 그래프로 간주하여 받은 뒤 루트를 1번 노드로하는 BFS 트리를 생성해준다.이 때 각 노드의 깊이를 함께 구해주도록 하자.만약, a와 b의 LCA를

2021년 12월 14일
·
0개의 댓글
·

2019 winter PS --version Basic (day26)

백준 11437 -- 1) 백준 11437 : LCA 아직 안품.

2020년 1월 29일
·
0개의 댓글
·