P14346 [JOISC 2019] 指定城市 / Designated Cities

JOI 国内共有 $N$ 座城市，城市编号从 $1$ 到 $N$。国内有 $N - 1$ 条道路，编号从 $1$ 到 $N - 1$。对于第 $i$ 条道路（$1 \le i \le N - 1$），它包含两条车道：一条从城市 $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$ 中，设 $a$ 为距离城市 $x$ 更近的城市，$b$ 为距离城市 $x$ 更远的城市。此处，“距离城市 $x$ 更近”是指从该城市出发，到达城市 $x$ 所需经过的道路数量更少。随后，从城市 $b$ 指向城市 $a$ 的车道将被铺设（若尚未铺设）。 因指定度假城市而产生的车道铺设费用将由税收支付。然而，指定后仍保持未铺设状态的车道的铺设费用需由 Mr. K 自掏腰包支付。 现共有 $Q$ 个方案提交给 Mr. K。在第 $j$ 个方案（$1 \le j \le Q$）中，他将从无任何度假城市、且所有道路的所有车道均未铺设的初始状态出发，并恰好指定 $E_j$ 座城市为度假城市。但具体指定哪些城市尚未确定。他希望知道，对于每个方案，需由他自掏腰包支付的最小总铺设费用是多少。 请编写一个程序，输入 JOI 国的城市数量、道路信息及各方案信息，计算并输出每个方案中需由 Mr. K 自掏腰包支付的最小总铺设费用。

从标准输入读取以下数据。输入中的所有值均为整数。 $N$ $A_1\ B_1\ C_1\ D_1$ $\vdots$ $A_{N-1}\ B_{N-1}\ C_{N-1}\ D_{N-1}$ $Q$ $E_1$ $\vdots$ $E_Q$

向标准输出写入 $Q$ 行。第 $j$ 行（$1 \le j \le Q$）应包含第 $j$ 个方案中需由 Mr. K 自掏腰包支付的最小总铺设费用。

### 样例 1 解释 考虑方案 1：Mr. K 将恰好指定 1 座城市为度假城市。若他指定城市 1 为度假城市，则道路 1 上从城市 2 指向城市 1 的车道、道路 2 上从城市 3 指向城市 1 的车道、以及道路 3 上从城市 4 指向城市 1 的车道将被铺设。因此，以下车道将保持未铺设状态：道路 1 上从城市 1 指向城市 2 的车道、道路 2 上从城市 1 指向城市 3 的车道、以及道路 3 上从城市 1 指向城市 4 的车道。铺设这些车道的总成本为 $1 + 3 + 5 = 9$。不存在任何指定方式能使总成本低于 9。因此，答案为 9。 考虑方案 2：Mr. K 将恰好指定 2 座城市为度假城市。若他指定城市 3 和城市 4 为度假城市，则道路 1 上从城市 1 指向城市 2 的车道将是唯一保持未铺设的车道。铺设该车道的成本为 1。不存在任何指定 2 座城市的方式能使总成本低于 1。因此，答案为 1。 ### 约束条件 - $2 \le N \le 200000$。 - $1 \le A_i \le N$（$1 \le i \le N - 1$）。 - $1 \le B_i \le N$（$1 \le i \le N - 1$）。 - $A_i \ne B_i$（$1 \le i \le N - 1$）。 - 任意两座城市之间均可通过道路相互到达。 - $1 \le C_i \le 1000000000$（$1 \le i \le N - 1$）。 - $1 \le D_i \le 1000000000$（$1 \le i \le N - 1$）。 - $1 \le Q \le N$。 - $1 \le E_j \le N$（$1 \le j \le Q$）。 ### 子任务 1. （6 分）$N \le 16$。 2. （7 分）$Q = 1$，$E_1 = 1$。 3. （9 分）$Q = 1$，$E_1 = 2$。 4. （17 分）$N \le 2000$。 5. （17 分）$Q = 1$。 6. （44 分）无额外约束。