题解：CF2152H1 Victorious Coloring (Easy Version)

BPG_ning · 2025-10-08 11:42:33 · 题解

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

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

具体来说，我们考虑一个类似贪心状的 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)。