시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 3 3 3 100.000%

문제

There are N cities in JOI Country. The cities are numbered from 1 to N. There are N − 1 roads, numbered from 1 to N − 1. The road i (1 ≤ i ≤ N − 1) contains two lanes: a lane from the city Ai toward the city Bi and a lane from the city Bi toward the city Ai. Thus, the all roads are bidirectional. It is possible to travel between any pair of cities by using roads.

Currently, all lanes of all roads are not paved. For each lane of each road, we know the cost to pave the lane. Of the road i (1 ≤ i ≤ N − 1), the cost to pave the lane from the city Ai toward the city Bi is Ci and the cost to pave the lane from the city Bi toward the city Ai is Di.

Mr. K, the Prime Minister of JOI Country, can choose some cities and designate them as resort cities. When he designates the city x (1 ≤ x ≤ N) as a resort city, the following event will occur to each road i (1 ≤ i ≤ N−1):

  • Of the cities Ai and Bi, let a be the nearer to the city x and let b be the farther. Here, the nearer city to the city x means the city from which the fewer number of roads are needed to pass through to reach the city x. Then, the lane from the city b toward the city a will be paved (if it has not been paved yet).

The cost of paving constructions of the lanes caused by designating resort cities will be financed from taxes. However, the cost of the paving constructions of the lanes left unpaved after the designation need be financed from Mr. K’s pocket money.

There are Q plans proposed to Mr. K. In the j-th (1 ≤ j ≤ Q) plan, he will start from the situation where there is no resort city and all lanes in all roads are not paved, and he will designate exactly Ej cities as resort cities. However, which cities to be designated is not determined yet. He wants to know for each plan the minimum total paving cost which need be paid from his pocket money.

Write a program which, given the number of cities in JOI Country, the information of the roads, and the information of the plans, calculates for each plan the minimum total paving cost which need be paid from Mr. K’s pocket money.

입력

Read the following data from the standard input. All the values in the input are integers.

N
A1 B1 C1 D1
.
.
.
AN−1 BN−1 CN−1 DN−1
Q
E1
.
.
.
EQ

출력

Write Q lines to the standard output. The j-th (1 ≤ j ≤ Q) line should contain the minimum total paving cost which need be paid from Mr. K’s pocket money for the j-th plan.

제한

  • 2 ≤ N ≤ 200 000.
  • 1 ≤ Ai ≤ N (1 ≤ i ≤ N − 1).
  • 1 ≤ Bi ≤ N (1 ≤ i ≤ N − 1).
  • Ai, Bi (1 ≤ i ≤ N − 1).
  • It is possible to travel between any pair of cities by using roads.
  • 1 ≤ Ci ≤ 1 000 000 000 (1 ≤ i ≤ N − 1).
  • 1 ≤ Di ≤ 1 000 000 000 (1 ≤ i ≤ N − 1).
  • 1 ≤ Q ≤ N.
  • 1 ≤ Ej ≤ N (1 ≤ j ≤ Q).

예제 입력 1

4
1 2 1 2
1 3 3 4
1 4 5 6
2
1
2

예제 출력 1

9
1

Consider the plan 1: Mr. K will designate exactly 1 city as a resort city. If he designates the city 1 as a resort city, the lane from the city 2 toward the city 1 of the road 1, the lane from the city 3 toward the city 1 of the road 2, and the lane from the city 4 toward the city 1 of the road 3 will be paved. Hence, the following lanes will be left unpaved: the lane from the city 1 toward the city 2 of the road 1, the lane from the city 1 toward the city 3 of the road 2, and the lane from the city 1 toward the city 4 of the road 3. The total cost of paving these lanes is 1 + 3 + 5 = 9. There is no way to designate a city so that the total cost is less than 9. Thus, the answer is 9.

Consider the plan 2: Mr. K will designate exactly 2 cities as resort cities. If he designates the city 3 and the city 4 as resort cities, the lane from the city 1 toward the city 2 of the road 1 will be the only lane to be left unpaved. The cost to pave this lane is 1. There is no way to designate 2 cities so that the total cost is less than 1. Thus, the answer is 1.

예제 입력 2

5
1 3 13 6
5 1 17 8
5 2 6 10
1 4 16 11
1
1

예제 출력 2

36

예제 입력 3

6
1 6 6 12
6 2 5 16
1 4 13 4
5 1 19 3
3 1 9 13
1
2

예제 출력 3

14