問題一覧 > 通常問題

No.386 The Greedy Lord

レベル : / AI推定難易度 : 1450 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 129
作問者 : horiesiniti / テスター : 37zigen
お気に入りにしたユーザー ProblemId : 1183 / 自分の提出
問題文最終更新日: 2026-10-16 14:34:39
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 140 (順位表) の他の問題:

Problem Statement

In a certain region, there was an area where points represent villages and lines represent highways, forming a tree structure.
The lord of that land was very greedy and decided to set up a checkpoint in every village.
Each time a peddler passes through a village, the peddler must pay a fixed toll per person.
You are the chief accountant hired by the lord.
You have been told to find, from the given data, the total amount of tax paid by all the peddlers.
Without worrying about anything, write a program that outputs the total amount of tax on one line.
What future the lord's greedy taxes will produce is not your concern.
(Note: so that you can try this problem casually, the tax amounts and the numbers of peddlers in the judge data are set to very small values. They are set so that the result fits in a 64-bit integer even with a very unusual aggregation.)
Given the village data and the peddlers' travel routes on the tree, compute the total tax revenue.

Input

$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$
The first line contains the number of villages $2\le N \le 100000$.
The following $N-1$ lines give the data for the highways connecting villages.
This means that villages $A_i$ and $B_i$ are connected by a highway, which can be traveled in both directions.
You may assume that the villages are numbered $0~N-1$.
The following $N$ lines give the toll set by the lord for each village, as integers $U_i$, in order from village $0$ to village $N-1$. Each is a natural number with $0\lt U_i \le 100$.
Next, one line contains the number of peddler data entries M as an integer, $0\le M \le 200000$.
Over the following M lines:
$A_i$ is the departure village, $0 \le A_i \le N-1$.
$B_i$ is the destination village, $0 \le B_i \le N-1$ , $A_i \neq B_i$.
$C_i$ is the number of peddlers making that trip. $1 \le C_i \le 10$
All peddlers must pay the toll at the departure village $A_i$, pay tax at the villages along the route, and pay tax at the destination village $B_i$.
In every village, the amount paid is for $C_i$ people.

Output

S

Sample

Sample 1
Input
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
Output
152

The peddlers going from village 2 to village 3 pay tax at villages 2,1,3.
(7+3+10)*4 people = 80
The peddlers heading from village 4 to village 6 pay tax at villages 4,7,0,6.
(5+9+2+8)*3 = 72
In this sample input, the tax paid by all the peddlers is 80+72 = 152.
Therefore, output 152 on one line.

Sample 2
Input
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
Output
1274

Sample 3
Input
2
0 1
11
7
2
0 1 3
1 0 2
Output
90

Sample 4
Input
3
0 1
1 2
13
11
7
3
1 0 2
0 2 3
0 2 5
Output
296

Separate groups may depart from the same town. Naturally, they are taxed separately.

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