# LCA

rootachieve

N개의 도시가 N-1개의 간선으로 두 도시간 경로가 유일하게 연결되어있다. 두 도시쌍이 여러개 들어올 때 두 도시를 연결하는 도로중 가장 긴 도로와 가장 짧은 도로를 구하시오

smsh0722

Tree에서 u, v의 LCA는, root로부터 가장 멀리(deepest) 있는 공통 조상이다. 그렇다면 어떻게 LCA를 구할 수 있을까? Method 1 Naive 하게 root에서 각 node까지의 경로를 비교하여 풀 수 있다. root에서 u, v까지의 경로를

smsh0722

시간 제한: 1초메모리 제한: 256MB먼저, 문제 상황은 트리의 특성을 갖고 있다. 따라서, 두 도시를 잇는 경로를 찾기 위해선, LCA를 찾으면 된다. 이후에, naive하게, 경로를 직접 따라가면서 최대와 최소를 구하는 방법은 최악의 경우 시간 복잡도가 O(N)이

smsh0722

시간 제한: 2초메모리 제한: 512MBroot가 계속 변하는 게 핵심이다. RMQ를 위해 pre-processing을 하는 데 O(N)의 시간 복잡도를 갖기에, 매번 새로 생성하는 건 불가능 하다. 하지만, 조금 더 분석을 해보면, 아래와 같이 처음에 1을 root로

smsh0722

시간 제한: 2초메모리 제한: 128MB두 정점을 잇는 경로를 찾아내야 한다. 이때, 두 정점을 잇는 최상단 node인 Lowest common ancestor(LCA)를 찾으면 경로를 쉽게 이을 수 있을 것이다.1번 node를 root로 하여, DFS를 진행하여 다음

wook2pp

https://www.acmicpc.net/problem/11438LCA는 Lowest Common Ancestor로 최소공통조상을 찾는 알고리즘이다. 두 노드의 최소공통조상을 찾는 방법은1\. 두 노드의 높이를 맞춘다.2\. 노드를 올려보면서 부모가 같은지

kldaji

문제링크LCA2 문제풀이를 참고해주세요.

kldaji

문제링크11437-LCA 풀이와 비슷하지만, 공통 부모를 찾는 과정에 차이점이 있습니다.node의 2^0, 2^1, ... 번째 parent를 저장합니다.항상 node2의 깊이가 더 깊다고 가정하고, 두 node의 깊이 차이를 통해 node2를 node1과 같은 깊이에

kldaji

문제링크dfs를 통해 각 node의 depth를 계산합니다.LCA를 구할 두 node의 depth를 동일하게 만듭니다.두 node의 parent가 같아질 때까지 두 node의 parent를 비교합니다.

tunaman95

루트가 있는 트리(rooted tree)가 주어지고, 그 트리 상의 두 정점이 주어질 때 그들의 가장 가까운 공통 조상(Nearest Common Anscestor)은 다음과 같이 정의됩니다.두 노드의 가장 가까운 공통 조상은, 두 노드를 모두 자손으로 가지면서 깊이가

tunaman95

최소 공통 조상(LCA) 문제는 두 노드의 공통된 조상 중에서 가장 가까운 조상을 찾는 문제다.위의 그래프에서 8번 노드와 15번 노드의 LCA는 2번 노드다.3번 노드와 15번 노드의 LCA는 1번 노드다.모든 노드에 대한 깊이(depth)를 계산한다.최소 공통 조상

jsin2475

매출 첫 6조 카카오…"3000억 자사주 소각" 주주 달래기카카오는 회사가 너무 커졌는데 나온는 얘기들도 너무 많은 것 같다.선점의 대표적 주자가 아닌가 싶다. 역시 돈 내고 쓰던거 무료로 쓰게 해주는 건우선적으로 할 경우 시장을 먹고 그렇게 뻗어 나가는 것이 가장 좋

silver_star

https://www.acmicpc.net/problem/3584루트 노드 찾기입력 트리 노드 정보가 "부모 노드 - 자식 노드" 형태로 주어짐트리 노드 정보 입력할 때, 자식 노드들을 방문 처리=> 입력이 끝난 후, 방문되지 않은 노드가 루트 노드1) 모든

jsin2475

https://www.acmicpc.net/problem/1626시간 2초, 메모리 128MBinput :V E(1 ≤ V ≤ 50,000, 1 ≤ E ≤ 200,000)u v w(0 <= w < 100,000)output : 두 번째로 작은 스패닝

jsin2475

https://www.acmicpc.net/problem/15481시간 2초, 메모리 512MBinput :N M (2 ≤ N ≤ 200,000, N-1 ≤ M ≤ 200,000)u v w (1 ≤ u, v ≤ n, u ≠ v, 1 ≤ w ≤ 10^9) out

gyrbs22

1. 최소공통조상 LCA, Lowest common ancestor. 두 노드의 공통된 상위 부모노드(조상) 중에서, 가장 가까운 부모노드를 의미한다. 위 graph(tree)에서 8번노드와 15번노드의 LCA는 2번노드가 된다. 2. 해 도출 과정 모든 노드

aram_father

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

jsin2475

https://www.acmicpc.net/problem/1761시간 2초, 메모리 128MBinput :N(2 ≤ N ≤ 40,000)N - 1개의 줄 : 트리 상에 연결된 두 점과 거리M(1 ≤ M ≤ 10,000)M개의 줄 : 한 쌍씩 입력output :

jsin2475

https://www.acmicpc.net/problem/11438시간 1.5초, 메모리 256MBinput :N(2 ≤ N ≤ 100,000)N-1개 줄 : 트리 상에서 연결된 두 정점M(1 ≤ M ≤ 100,000)M개 줄에는 정점 쌍output : 첫 줄