예를 들어, 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)의 방법을 생각해야 문제를 푸실 수 있습니다.