P12423 【MX-X12-T6】「ALFR Round 5」Coloring Nodes

原题链接：。

给定一棵 $n$ 个点的树，初始时所有结点为白色。 你可以花费 $w_u$ 的代价将结点 $u$ 染黑。 有 $q$ 次询问，每次询问形如 `u l r`。对于每次询问，你需要花费尽可能小的代价，将一些结点染黑，使得点 $u$ 到**叶结点** $v$ 的简单路径上存在黑色结点，**当且仅当** $l \le v \le r$，并输出最小代价。

无

无

**【样例解释 #1】** 该样例满足特殊性质 A。 对于第一次询问，染黑 $2$ 号点，最小代价为 $3$； 对于第二次询问，染黑 $3$ 号点，最小代价为 $1$； 对于第三次询问，染黑 $1$ 号点，最小代价为 $4$； 对于第四次询问，染黑 $3$ 号点，最小代价为 $1$。 **【样例解释 #2】** 该样例满足特殊性质 B。 对于第一次询问，染黑 $3$ 号点，最小代价为 $1$； 对于第二次询问，染黑 $2,4,6,7$ 号点，最小代价为 $-19$； 对于第三次询问，可证明没有可行的染色方案。 **【数据范围】** **本题使用捆绑测试。** 对于 $100\%$ 的数据，$1 \le n, q \le 2 \times 10^5$，$|w_u| \le 10^9$，$1 \le u, v \le n$，$1 \le l \le r \le n$。 |子任务编号|$n \le$|$q \le$|特殊性质|分值|子任务依赖| |:-:|:-:|:-:|:-:|:-:|:-:| |$1$|$20$|$20$|无|$5$|-| |$2$|$20$|$2 \times 10^5$|无|$5$|$1$| |$3$|$8000$|$8000$|A|$5$|-| |$4$|$8000$|$8000$|无|$5$|$3$| |$5$|$8000$|$2 \times 10^5$|A|$10$|$3$| |$6$|$8000$|$2 \times 10^5$|无|$10$|$2, 4, 5$| |$7$|$2 \times 10^5$|$2 \times 10^5$|AB|$10$|-| |$8$|$2 \times 10^5$|$2 \times 10^5$|A|$15$|$5, 7$| |$9$|$2 \times 10^5$|$2 \times 10^5$|B|$15$|$7$| |$10$|$2 \times 10^5$|$2 \times 10^5$|无|$20$|$6, 8, 9$| 特殊性质 A：$w_u \ge 0$。 特殊性质 B：对于所有询问，$u=1$。