問題文

ある地方では点が村に、街道が線で木構造をなしている地域がありました。
その土地の領主はとても貪欲で全ての村に関所を設けることとなりました。
行商人は村を通るたびに一人頭一定額の通行税を納めることになります。
貴方は領主に雇われた会計主任です。
与えられたデータから行商人全員が納める税額の総計を求めるように言われました。
貴方は何も気にせず税額の総計を一行に出力するプログラムを書いてください。
領主の貪欲な税がどんな未来を算出するのか、それは貴方が気にすることではありません。
（注、気楽に挑戦してもらうために採点データは税や行商人の人数は非常に小さい値に設定した。非常に特殊な集計をしても６４ビット整数値に収まるように設定している）
村のデータと行商人の木構造上での移動ルートが与えられるので税収の総額を計算せよ。

入力

$N$
$A_1{B}_1$
$\dots$
$A_i{B}_i$
$\dots$
$A_{N-1}{B}_{N-1}$
$U_1$
$\dots$
$U_i$
$\dots$
$U_N$
$M$
$A_1{B}_1{C}_1$
$\dots$
$A_i{B}_i{C}_i$
$\dots$
$A_M{B}_M{C}_M$

出力

S

サンプル

サンプル1

入力サンプルをコピー

入力

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

出力

152

村2～村3へ行く行商人は村2,1,3で税を払う。
（7+3+10）*4人＝80
村4～村6へ向かう行商人は村4,７,0,6で税を払うので。
（5+9+2+8）*3＝72
このサンプルインプットでは行商人全員のはらう税は80+72＝152となる。
よって152と一行に出力すること。

サンプル2

入力サンプルをコピー

入力

22
10 11
10 12
13 14
13 15
13 16
17 18
17 19
19 20
19 21
0 1
0 9
0 13
1 2
1 17
2 3
2 5
3 4
3 8
5 6
5 7
9 10
3
5
8
6
4
11
13
7
2
10
3
5
12
4
11
3
17
2
1
7
9
11
15
0 16 3
0 21 4
3 4 2
3 5 2
6 4 3
7 0 1
9 13 3
11 1 4
11 14 2
12 16 2
12 8 3
14 13 1
14 18 2
16 2 6
19 5 3

出力

1274

サンプル3

入力サンプルをコピー

入力

2
0 1
11
7
2
0 1 3
1 0 2

出力

90

サンプル4

入力サンプルをコピー

入力

3
0 1
1 2
13
11
7
3
1 0 2
0 2 3
0 2 5

出力

296

同じ町から別々のグループが出発することもあります。 当然別々に課税されます。