BOJ 1289 트리의 가중치

트리의 성질 중 하나가 어느 두 정점 간에도 유일하게 하나의 경로가 존재한다는 것인데, 경로의 가중치를 경로에 해당하는 간선들의 가중치 곱으로 정의할 때, 모든 경로의 가중치들의 합인 트리의 가중치를 구하는 문제이다.

N제한이 10만인데, N개의 정점 중 2개의 정점을 선택하는 경우는 N C 2 = N*(N-1)/2 이다.
직접 곱을 다 구해서 합을 구하기에는 N이 너무 크다.
그렇다면 어떻게 해야할까? 구하고자 하는 것이 모든 경로의 가중치들의 합이기 때문에 분명 뭔가 규칙이 있을 것 같다.
일단 규칙을 찾기 위해 작은 트리를 내가 직접 그려 봐야겠다. 음 잘 모르겠다...
일단 빌라봉 문제를 통해 트리에 대해 공부했던 것이 거의 기억이 안난다. 일단 이참에 빌라봉부터 다시 공부해보고 풀어 봐야겠다.