#3036. 「JOISC 2019 Day3」指定城市

内存限制:512 MiB 时间限制:2000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: EntropyIncreaser

题目描述

题目译自 JOISC 2019 Day3 T1「指定都市 / Designated Cities

JOI 国有 N 座城市。编号从 1 N 。国内有 N - 1 条道路,编号从 1 N - 1 。第 i 条路包含两条车道:从城市 A_i 向城市 B_i 方向的和从城市 B_i 向城市 A_i 方向的。于是这些道路都可以双向行驶。并且这些道路使得可以从任何一个城市到达另外任何一个城市。

现在所有的车道都还没有铺好。对于第 i (1\le i\le N - 1) 条路,从 A_i B_i 的车道的铺设代价是 C_i ,从 B_i A_i 的铺设代价是 D_i

JOI 国的首相 Mr. K 可以选择一些城市并且将其指定为度假城市。当他指定城市 x(1\le x\le N) 为度假城市时,对于每条路 i(1\le i\le N-1) 会发生如下事件:

  • 设城市 A_i, B_i 中离城市 x 较近的为 a ,较远的为 b 。这里离 x 较近的城市的意思是从这个城市到 x 城市经过的道路数比另一个少。若 b a 方向的车道还未被铺设,则现在要将其铺设,因为这意味着这是一条可以通向度假城市的车道。

对于这些通向度假城市的车道的建设,经费会从纳税中拨款,而剩下的车道的铺路费则要由 Mr. K 自掏腰包。

接下来 Mr. K 提出了 Q 个计划。第 j\:\!(1\le j\le 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

样例输出 1

9
1

样例解释 1

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

对于计划 2 ,Mr. K 可以选定 3, 4 号城市,这样他要自掏腰包的车道就是 1\rightarrow 2 。总花费为 1

样例输入 2

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

样例输出 2

36

样例解释 2

这组样例满足子任务 2 的限制。

样例输入 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

样例解释 3

这组样例满足子任务 3 的限制。

样例输入 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

样例输出 4

44
12
6

数据范围与提示

限制

  • 2\le N \le 2\times 10^5
  • 1\le A_i, B_i\le N (1\le i\le N - 1)
  • 保证城市两两可到达
  • 1\le C_i, D_i\le 10^9 (1\le i\le N - 1)
  • 1\le Q\le N
  • 1\le E_j\le N(1\le j\le Q)

子任务

Subtask # 分值 N \le Q 特殊限制
1 6 16 \le N
2 7 2\times 10^5 =1 E_1=1
3 9 E_1=2
4 17 2000 \le N
5 2\times 10^5 =1
6 44 \le N