트리의 경로 가중치 합
시간 제한2초메모리 제한128 MB
가중치가 있는 트리에서 모든 정점 쌍의 경로에 있는 간선 가중치들의 곱을 모두 더한 값을 1,000,000,007로 나눈 나머지를 구합니다.
문제
정점 N개와 간선 N - 1개로 이루어진 트리가 주어진다. 트리에서는 서로 다른 두 정점 사이에 단 하나의 단순 경로만 존재한다.
각 간선에는 음이 아닌 정수 가중치가 하나씩 있다. 한 경로의 가중치는 그 경로에 포함된 모든 간선 가중치의 곱으로 정의한다. 트리의 가중치는 서로 다른 두 정점 쌍을 잇는 모든 경로의 가중치를 더한 값이다.
트리가 주어졌을 때 트리의 가중치를 구하라.
입력
첫째 줄에 정점의 개수 N이 주어진다. (1 <= N <= 100,000)
다음 N - 1개 줄에는 세 정수 A B W가 주어진다. 이는 정점 A와 정점 B가 가중치 W인 간선으로 연결되어 있음을 뜻한다. (1 <= A, B <= N, 0 <= W <= 1,000)
출력
트리의 가중치를 1,000,000,007로 나눈 나머지를 출력한다.