아무리 고민해도 이문제는 못풀겠네요...힌트좀 주실수 없을까요??

jyuno426   4주 전

트리의 모든 경로는 O(N^2)개가 있으니 모든 경로를 각각 고려하는 방식으로는 문제 해결이 어렵습니다. 따라서 이미 탐색한 경로를 이용해 다른 경로를 해결해야 합니다.

예를 들어, A------B------C라는 path의 cost를 구하기 위해 부분경로인 A------B  path와 B------C path의 cost를  곱하면 됩니다.


트리의 root r, r의 서브트리 t1, t2, ... , tk를 생각해봅시다.

r을 포함하지 않는 경로들은 t1, t2, ... , tk에 대한 부분 문제로 해결하고,
r을 포함하는 경로들은 t1, t2 , ... , tk를 탐색하면서 "r을 끝 점으로 하는 경로"들에 대한 정보를 얻어 내어 이것들을 서로 이어주면서 해결할 수 있습니다. 이어주는 과정을 naive하게 생각하면 O(k^2)이지만 O(k)의 방법을 생각해야 문제를 푸실 수 있습니다.


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