(구현 방법은 나정휘 블로그 참고)

• O(N)에 센트로이드를 지나는 모든 경로를 봐줄 수 있는가? ⇒ O(NlogN)에 계산 가능
• 노드 u에 대해서 모든 u→v 경로를 봐야 하는가? ⇒ 센트로이드 트리로 O(logN)에 가능
• 쿼리 당 O(logN) 이내에 모든 경로에 대한 값을 구해야 하는가? ⇒ O(logN)에 노드가 속한 모든 서브트리에서의 답을 업데이트하고 multiset 하나에 때려박아놓기