dh_0e

LCA와 쿼리 2 (백준 15480번) 어떤 트리의 root를 계속해서 바꾸면서 LCA를 구하는 쿼리를 해결하는 문제로, LCA를 최대 100,'000번 구성하도록 코드를 짜면 무조건적으로 시간초과가 나온다. 수학적 패턴이나 조건 분기들을 따져야 하는 문제 같아서 계속 고민해 봤지만 발상이 쉽지 않았다. 풀이 과정 LCA(r, a)와 LCA(r, b), LCA(a, b)의 값을 비교하여 답을 쉽게 도출할 수 있다.LCA(r, a)와 LCA(r, b)가 같다면 LCA(a, b)가 root를 r로 바꾼 트리의 최소 공통 조상이 된다.이 경우엔, a부터 b로의 경로 중에 r이 없다는 뜻으로 root를 r로 바꾸어도 LCA는 그대로 LCA(a, b)가 된다.그렇지 않다면, LCA(r, a)와 LCA(r, b) ..

도로 네트워크 (백준 3176번) LCA 2(백준 11438번)처럼 희소 배열을 이용한 최소 공통 조상(Binary Lifting) 알고리즘을 활용한 문제. [PS] LCA 2 / C++ (백준 11438번)희소 배열(Sparse Table)을 사용해 LCA를 O($logn$)만에 구해야한다. 일반적으로 희소 배열을 사용하면 O(n)이 걸리기 때문에 Binary Lifting 방식으로 공통 조상을 찾는 과정이 필요하다. 풀이 과정1. 우선 dfdh-0e.tistory.com구현이 꽤 복잡하지만 설계를 잘 하고, LCA를 적절하게 구현하면 쉽게 풀 수 있다. #include#include#includeusing namespace std;vector> vec[100001];int depth[100001],..