P11324 【MX-S7-T2】「SMOI-R2」Speaker

原题链接：。

M 国有 $n$ 个城市和 $n - 1$ 条双向道路，城市编号为 $1,2,\dots,n$，**保证这些城市连通**，即**构成了一棵树**。其中，第 $i$ 条道路连接了城市 $u_i$ 和城市 $v_i$，路费为 $w_i$。你是一名演说家，每天都要在 M 国举办三场演讲，每场演讲都会在某一个城市进行。在城市 $i$ 举办一场演讲可以获得 $c_i$ 的收入，**同一天内可以在同一个城市举办多场演讲**。 接下来有 $q$ 天，第 $i$ 天的安排如下：你的第一场演讲必须在城市 $x_i$ 举行，第三场演讲必须在城市 $y_i$ 举行，而第二场演讲所在的城市可以自由选择。设第二场演讲所在的城市为 $z_i$，你需要向交通管理局支付经过 $x_i \to z_i$ 路径以及 $z_i \to y_i$ 路径上所有道路的路费。**注意，一条道路如果被多次经过，每次经过都需要支付相应的路费**。 对于每一天，请计算当天可以获得的最大利润，即**总收入减去总路费的最大值**。**注意，答案可能是负数**。

无

无

**【样例解释 #1】** + 第一天选择城市 $1$，答案为 $4 + 4 + 4 - 0 - 0 = 12$。 + 第二天选择城市 $4$，答案为 $2 + 7 + 7 - 6 - 0 = 10$。 + 第三天选择城市 $2$，答案为 $2 + 6 + 2 - 2 - 2 = 6$。 **【样例 #2】** 见附件中的 `speaker/speaker2.in` 与 `speaker/speaker2.ans`。 该组样例满足测试点 $7\sim 8$ 的约束条件。 **【样例 #3】** 见附件中的 `speaker/speaker3.in` 与 `speaker/speaker3.ans`。 该组样例满足测试点 $11\sim 13$ 的约束条件。 **【样例 #4】** 见附件中的 `speaker/speaker4.in` 与 `speaker/speaker4.ans`。 该组样例满足测试点 $17\sim 19$ 的约束条件。 **【数据范围】** 对于所有测试数据，保证：$1\le n, q\le 2\times 10^5$，$1\le u_i, v_i \le n$，$0\le w_i, c_i\le 10^9$，所有城市和道路构成了一棵树，$1\le x_i, y_i \le n$。 |测试点编号|$n\le $|$q\le $|特殊性质| |:-:|:-:|:-:|:-:| |$1\sim 4$|$400$|$400$|无| |$5$|$2000$|$2000$|A| |$6$|$2000$|$2000$|B| |$7\sim 8$|$2000$|$2000$|无| |$9$|$2000$|$2\times 10^5$|A| |$10$|$2000$|$2\times 10^5$|C| |$11\sim 13$|$2000$|$2\times 10^5$|无| |$14\sim 15$|$2\times 10^5$|$3$|无| |$16$|$2\times 10^5$|$2\times 10^5$|A| |$17\sim 19$|$2\times 10^5$|$2\times 10^5$|C| |$20\sim 25$|$2\times 10^5$|$2\times 10^5$|无| - 特殊性质 A：每个城市至多被两条道路连接。 - 特殊性质 B：存在一座城市 $i$（$1\le i\le n$），满足对于所有其他城市 $j$（$1\le j\le n$、$j \ne i$），都存在连接城市 $i$ 与城市 $j$ 的道路。 - 特殊性质 C：对所有 $1 \le i \le q$，都有 $x_i = 1$。