mkleeboy3   11달 전

안녕하세요. 메모리 초과가 자꾸 떠서 질문드립니다.

방식은 다음과 같이 했습니다.

1. 인접리스트로 트리 작성

2. DFS로 한번씩 돌면서 각 노드별 부모 파악, 루트에서부터 깊이(루트 깊이 0으로 설정) 파악

3. LCA 함수를 이용하여 페어의 원소 u, v의 공통 조상을 조사

     - 여기서 DP 동적배열을 이용하여 u 또는 v를 처음 조사하는거면 그 처음 조사하는 노드의 직속 부모를 타고 올라가 루트까지의 경로를 담음

     - 그 다음에 DP를 이용하여 O(height) 시간안에 계산

DP배열을 없애서 모든 페어를 직속 부모 체인 형식으로 올라가면 시간초과 뜨구요.. 몇 시간째 고민중인데 참 힘드네요. 다른 방법이 있는건가요?

도움 주시면 진심으로 감사하겠습니다.

mkleeboy3   11달 전

binary lifting 이라는 기법을 쓰면 되는군요.

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