26159번 - 트리와 수열

$N$개의 정점으로 구성된 트리가 있다. 각 정점은 $1$번부터 $N$번까지 번호가 매겨져 있다. 또한 $N-1$개의 음이 아닌 정수로 이루어진 수열이 있다.

트리의 간선에 수열의 원소들을 하나씩 대응시켜 가중치를 매길 것이다. 이때 가능한 ${\sum dist(i,j)}$ $(1 \leq i < j \leq N)$의 최솟값을 $10^9+7$로 나눈 나머지를 구하려고 한다.

$dist(i,j)$는 트리의 $i$번 정점과 $j$번 정점 사이의 단순 경로 상 가중치의 합을 의미한다.

첫 번째 줄에 정점의 개수 $N$이 주어진다. $(2 ≤ N ≤ 100\ 000)$

이후 $N-1$개의 줄에 걸쳐 트리의 각 간선이 연결하는 두 정점 $u, v$가 공백으로 구분하여 주어진다. $(1 \leq u, v \leq N)$

다음 줄에 수열의 원소 $a_1,\cdots,a_{N-1}$이 공백으로 구분하여 주어진다. $(1 ≤ a_i ≤ 10^9;$ 모든 $a_i$ 는 정수$)$

${\sum dist(i,j)}$ $(1 \leq i<j \leq N)$의 최솟값을 $10^9+7$로 나눈 나머지를 출력하라.