No.386 The Greedy Lord
タグ : / 解いたユーザー数 129
作問者 :
horiesiniti
/ テスター :
37zigen
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もしくは右上の雲マークをクリックしてアカウントを作成してください。