アリの巣

問題文

競技プログラミング部 Ants部員のmomoyuu君はアリの巣を観察するのが大好きです。今観察しているアリの巣には部屋が $N$ 個あるのでmomoyuu君は部屋 $1$ から部屋 $N$ まで番号付けることにしました。

部屋同士を双方向につなぐ通路が $N-1$ 本あり、 $i$ 番目の通路は部屋 $a_i$ と部屋 $b_i$ をつないでいます。また、momoyuu君の観察によると、どの部屋からどの部屋へもいくつかの通路を通って到達できる事が分かりました。

さらに観察を進めると、それぞれの部屋には餌が $1$ つずつあり、部屋 $i$ には種類 $c_i$ の餌があることが分かりました。

そこでmomoyuu君は整数の組 $(i,j) (1 \leq i,j \leq N)$ に対して、

$score(i,j) =$ $($部屋 $i$ から部屋 $j$ までの最短経路で通る通路の数$)$ $\times$ $($部屋 $i$ から部屋 $j$ までの最短経路で通る部屋にある餌の種類数$)^2$

という点数を付けました(問題の条件下では部屋 $i$ から部屋 $j$ への最短経路が一意に定まることが証明できます)。

この時、

$\displaystyle \sum_{i=1}^{N} \sum_{j=1}^{N} score(i,j)$

を求めてください。

制約

• $2 \leq N \leq 10^5$
• $1 \leq a_i < b_i \leq N \ (1 \leq i \leq N-1)$
• $1 \leq c_i \leq 6 \ (1 \leq i \leq N)$
• 入力は全て整数

入力

入力は以下の形式で標準入力で与えられる。

出力

答えを出力せよ。

サンプル

5
1 2
1 3
3 4
3 5
1 2 3 4 5

368

例えば、
$score(1,2) = 1 \times 2^2 = 4$
$score(1,4) = 2 \times 3^2 = 18$
$score(5,5) = 0 \times 1^2 = 0$
となります。

7
2 4
5 7
1 4
4 6
3 4
2 7
5 1 4 1 3 4 3

606

10
1 8
5 6
2 10
1 9
8 10
5 8
3 5
7 10
1 4
1 5 6 5 6 2 2 6 1 6

1492