問題一覧 > 通常問題

No.386 貪欲な領主

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 122
作問者 : 👑 horiesinitihoriesiniti / テスター : 37zigen37zigen
3 ProblemId : 1183 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2016-07-02 01:32:54

問題文

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

入力

$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$
一行目に村の数$2\le N \le 100000$
続く$N-1$行に村と村をつなぐ街道を現すデータが与えられます。
意味は$A_i$と$B_i$の村が街道でつながっており双方向に移動可能。
村は$0~N-1$までの番号が割り振られていると仮定してよい。
続く$N$行に、領主の定めた各村の通行税の額が村$0$~村$N-1$まで順番に整数$U_i$で与えられる。 $0\lt U_i \le 100$の自然数
次に行商人のデータ数Mが一行に整数で$0\le M \le 200000$
続くM行にわたり
$A_i$は出発の村 $0 \le A_i \le N-1$
$B_i$は目的の村 $0 \le B_i \le N-1$
$C_i$はその移動をする行商人の人数です。$1 \le C_i \le 10$
行商人は全て出発の村$A_i$で通行税を納め途中経路の村村で税を納め目的の村$B_i$で税を納める必要があります。
それもどこでも$C_i$人分です。

出力

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,7,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

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

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。