hyunynim   2년 전

LCA를 구한 후 두 정점에서 시작해서 LCA와 만나기까지 하나씩 올라가면서 각 경로의 최대 최소를 비교해서 답을 구해냈는데

쿼리를 구하는 시간복잡도가 O(깊이)가 나와서 시간초과가 뜨는 것 같습니다.

도로의 최대 최소를 조금 더 효율적으로 구할 수 있는 방법이 있을까요???

kjp4155   2년 전

LCA를 구하는 과정에서

pa[k][x] : x의 2^k번째 부모

를 사용해서 시간복잡도 log(N)만에 LCA를 구하셨나요?


위 pa배열과 비슷하게, 

mn[k][x] : x에서 2^k번째 부모까지 올라가는 길에 있는 가장 짧은 도로의 길이

mx[k][x] : x에서 2^k번째 부모까지 올라가는 길에 있는 가장 긴 도로의 길이

를 만들어 주면 LCA구하는 과정에서 LCA까지 올라가는 가장 짧은 도로, 긴 도로의 길이를 각각 log(N)만에 구할 수 있을거에요

hyunynim   2년 전

질문올리고 컴퓨터를 확인을 오래 못해서 댓글을 이제야 봤습니다.

하루종일 고민하면서 비슷한 결론을 겨우 내렸네요. 

조언 감사합니다.

댓글을 작성하려면 로그인해야 합니다.