3036 「JOISC 2019 Day3」指定城市

题目译自 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$，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 的限制。

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

限制

• $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)$

子任务