指定城市
题号：NC53278
时间限制：C/C++/Rust/Pascal 2秒，其他语言4秒
空间限制：C/C++/Rust/Pascal 1024 M，其他语言2048 M
64bit IO Format: %lld

题目描述

题目译自 JOISC 2019 Day3 T1「指定都市 / Designated Cities」
JOI国有N座城市。编号从1到N。国内有N-1条道路，编号从1到N-1。第i条路包含两条车道：从城市A_i向城市B_i方向的和从城市B_i向城市A_i方向的。于是这些道路都可以双向行驶。并且这些道路使得可以从任何一个城市到达另外任何一个城市。
现在所有的车道都还没有铺好。对于第条路，从A_i到B_i的车道的铺设代价是C_i，从B_i到A_i的铺设代价是D_i。
JOI国的首相Mr.K可以选择一些城市并且将其指定为度假城市。当他指定城市为度假城市时，对于每条路会发生如下事件：
  • 设城市A_i,B_i中离城市x较近的为a，较远的为b。这里离x较近的城市的意思是从这个城市到x城市经过的道路数比另一个少。若b到a方向的车道还未被铺设，则现在要将其铺设，因为这意味着这是一条可以通向度假城市的车道。对于这些通向度假城市的车道的建设，经费会从纳税中拨款，而剩下的车道的铺路费则要由Mr.K自掏腰包。
接下来Mr.K提出了Q个计划。第个计划中，他要指定E_j个城市作为度假城市。然而，他还没决定具体指定哪E_j个城市。他想知道对于每个计划，所可能的自己出资的最小总花费。

输入描述:

第一行一个正整数N，表示城市的数量。
接下来N-1行，其中第i行四个整数A_i,B_i,C_i,D_i。意义见题目描述所示。
接下来一行一个正整数Q，表示计划数量。
接下来Q行，其中第j行一个正整数E_j，表示指定的城市数量。

输出描述:

输出Q行，每行一个正整数，表示可能的最小总代价。
示例1

输入

复制 
4
1 2 1 2
1 3 3 4
1 4 5 6
2
1
2

输出

复制 
9
1

说明

对于计划1，Mr.K可以选定1号城市，于是他需要自掏腰包的车道就是1 \rightarrow2,1 \rightarrow3,1 \rightarrow4。总花费是1+3+5=9。
对于计划2，Mr.K可以选定3,4号城市，这样他要自掏腰包的车道就是1 \rightarrow2。总花费为1。
示例2

输入

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

输出

复制 
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

输出

复制 
14
示例4

输入

复制 
15
14 5 12 7
14 12 6 5
14 10 14 16
9 14 16 12
13 7 4 15
1 3 8 1
6 7 15 13
15 4 4 6
9 1 12 6
13 1 7 6
13 4 5 15
2 6 11 19
8 4 12 7
13 11 14 5
3
3
6
7

输出

复制 
44
12
6

备注:

限制
保证城市两两可到达

CC-BY-SA，感谢LOJ分享，译文来自 https://loj.ac/problem/3036