Tree

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

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

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

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

시간 제한: 2초메모리 제한: 128MB먼저, 각 node의 위치를 구해야 한다. 이는 (왼쪽 자손의 수) + (현 node의 범위 왼쪽 끝)으로 구할 수 있다. In-Order DFS를 이용하면 된다.(l, .., ) 구간에 존재할 수 있는 현재 node의 위치를 다