問題文

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

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

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

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

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

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

この時、

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

を求めてください。

制約

  • 2N1052 \leq N \leq 10^5
  • 1ai<biN (1iN1)1 \leq a_i < b_i \leq N \ (1 \leq i \leq N-1)
  • 1ci6 (1iN)1 \leq c_i \leq 6 \ (1 \leq i \leq N)
  • 入力は全て整数

入力

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

NN
a1a_1b1b_1
a2a_2b2b_2
\vdots
aN1a_{N-1}bN1b_{N-1}
c1c_1c2c_2\ldotscNc_N

出力

答えを出力せよ。

サンプル

入力例1
5
1 2
1 3
3 4
3 5
1 2 3 4 5
出力例1
368

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

入力例2
7
2 4
5 7
1 4
4 6
3 4
2 7
5 1 4 1 3 4 3
出力例2
606
入力例3
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
出力例3
1492

提出


Go (1.21)