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 5년 전
LCA를 구한 후 두 정점에서 시작해서 LCA와 만나기까지 하나씩 올라가면서 각 경로의 최대 최소를 비교해서 답을 구해냈는데
쿼리를 구하는 시간복잡도가 O(깊이)가 나와서 시간초과가 뜨는 것 같습니다.
도로의 최대 최소를 조금 더 효율적으로 구할 수 있는 방법이 있을까요???