题解：CF2152H1 Victorious Coloring (Easy Version)

怄哥秒杀题，看题解后拼尽全力会了。

首先考虑求最小染色方案，发现最小染色方案中红色点一定构成连通块。于是我们能想到枚举连通块的根。

具体来说，我们考虑一个类似贪心状的 dp：设 $f_{i}$ 表示连通块以 $i$ 为根的染色方案的 $\geq l$ 的最小值。没错，我们不关心 $x_i$ 和 $\sum x_i$。

考虑转移。对于 $i$ 的每个儿子 $j$ 考虑其颜色：红色的贡献为 $f_{j}$；黄色的贡献为 $w_{i,j}$。所以有 $\sum \min(f_j,w_{i,j})+x_i+w_{i,\text{fa}_i}\geq l$，我们就可以求出 $x_i$ 的最小值，我们令 $x_i$ 等于其最小值即可。

这看起来很像一个假贪心，但是它是对的，考虑我们可以通过调整法使得每个点都选到他的当前最小值。

时间复杂度 $O(qn)$。