PST 한 개에 node i에 대해, i와의 LCA가 j인 node들의 갯수를 treei[j]에 저장하고, 나머지 PST에는 Euler tour 과정 중 node i를 방문하면 treein[i][i]에 1을 저장해 첫 번째 PST로는 k-th ancestor, 두 번째 PST로는 k-th descendant를 이분탐색으로 구하는 방식으로 문제를 해결하고자 했습니다.
해당 풀이의 시간복잡도는 O((N+Q)logN)으로 생각되나, 실제로 코드를 제출해봤을 때 TLE를 받게 되었습니다.
혹시 제가 풀이 상에서 놓치고 있는 부분이 있을지, 아니면 구현의 문제인지 모르겠어 질문을 드립니다.
혹시 몰라 말씀드리자면, 해당 풀이에서 vector 대신 배열로 PST를 구현한 코드와 map을 삭제한 버전의 코드 모두 TLE를 받았습니다.
감사합니다.
수정: 답변이 삭제된 것 같아 남깁니다. 121번째 줄에서 par[t] == l인 t를 찾는 과정에서 TLE을 받은 것으로 확인했습니다. 해당 부분을 binary lifting을 사용하는 방향으로 수정하니 AC를 받았습니다.
powerdavid10 10달 전
혼자서 고민하다 도저히 모르겠어 이렇게 글을 남기게 되었습니다.
PST 한 개에 node i에 대해, i와의 LCA가 j인 node들의 갯수를 treei[j]에 저장하고, 나머지 PST에는 Euler tour 과정 중 node i를 방문하면 treein[i][i]에 1을 저장해 첫 번째 PST로는 k-th ancestor, 두 번째 PST로는 k-th descendant를 이분탐색으로 구하는 방식으로 문제를 해결하고자 했습니다.
해당 풀이의 시간복잡도는 O((N+Q)logN)으로 생각되나, 실제로 코드를 제출해봤을 때 TLE를 받게 되었습니다.
혹시 제가 풀이 상에서 놓치고 있는 부분이 있을지, 아니면 구현의 문제인지 모르겠어 질문을 드립니다.
혹시 몰라 말씀드리자면, 해당 풀이에서 vector 대신 배열로 PST를 구현한 코드와 map을 삭제한 버전의 코드 모두 TLE를 받았습니다.
감사합니다.
수정: 답변이 삭제된 것 같아 남깁니다. 121번째 줄에서 par[t] == l인 t를 찾는 과정에서 TLE을 받은 것으로 확인했습니다. 해당 부분을 binary lifting을 사용하는 방향으로 수정하니 AC를 받았습니다.