트리 DP로 보고 여러가지로 접근해봤지만, 아무리 해도 O(n^2) 아래로 시간복잡도를 떨어뜨릴 수가 없었습니다.

약간의 힌트를 주시면 감사하겠습니다 ㅠ.ㅠ

해본 접근으로는

a[i]: i를 루트로 갖는 서브트리의 깊이

b[i]: i를 포함하는 경로의 최대 길이

라던가,

a[i]: i를 루트로 갖는 서브트리의 깊이

b[i]: i를 루트로 갖는 가장 깊은 서브트리의 가중치 총합

등등 여러가지로 생각해봤지만 시간복잡도를 O(n^2) 아래로 낮출 방법이 떠오르지 않네요...