CF2219C Coloring a Red Black Tree 题解

非常好题目。

注意到，你目前的最优策略只和当前的红点集合有关。而操作失败并不会改变红点集合。因此你的最优操作肯定是对着一个点一直操作直到成功为止。相当于我们要给所有点排出来一个顺序。

记作 为初始红点邻居个数和排在 前面的邻居个数之和。换句话说， 是已经将 前面所有的节点染色完毕时， 周围红色节点的个数。

这个点对期望做出的贡献就是 （一次操作成功概率是 ，操作失败不改变红点集合，到成功为止的期望就是 ）。

我们希望最小化 。有两种方法解决。

下文的所有 都表示在原图中的度数。

DP ver.

不妨转化成给树上的边定向，按照拓扑序输出方案。实际上的 就是入度。此时我们只要考虑周围的节点哪些是指出去的即可。

考虑任意指定一个根节点，令 分别表示 子树内定向好的最优方案， 到父节点的连边是指向 还是指向父节点。如果指向 ，说明父亲会给 贡献一个红色邻居。否则 会给父亲贡献一个红色邻居。

转移的时候可以考虑子树所有边都是指向自己的。从指向自己切换到指向儿子会产生 的代价，按照这个代价排序选择最小的即可。

假设从儿子中选择了 条指出去的边，对于 的情况，这个点的贡献就是

对于 的情况，会少一条来自父亲的边，这个点的贡献就是

对指向自己和指向父亲的情况做两次转移。需要注意对于 的情况，至少要保证周围有一个红点或者一条边指向自己，否则分母会为 ，转移非法。

此时不建议直接使用浮点计算得到的 inf，可能带来问题。应当直接跳过或者设置为一个极大值（比如 1e100）。

贪心 Ver.

直觉上，度数越多的节点应该往后放，等周围红色节点比较多时再染色。但是如果这个点一开始就有很多的红色节点，有可能立刻染就是最优的。

这启示我们建立一个偏序关系，并且按照这个顺序染色。对于“排序一个序列使得代价最小”的问题通常可以考虑这个，这就是被临项交换称作临项交换的技巧。

考虑交换相邻两个点 。令 表示染红了 前面所有的点之后，两个点周围的红色节点数量。我们要比较 和 的大小。

做差简单推一下式子就会发现 ，那么 应该放前面。

然而， 是在交换过程中改变的。上面定义的关系并不满足全序关系。因而临项交换并不适用这个题目。

我们继续考虑边定向的思路。实际上有很多顺序是本质相同的，对应到边定向上都是一样的。考虑我们的交换实际上意味着什么。

实际上，我们就是反转了一条边的方向。

进一步观察可以发现，不止是反转一条边的方向，如果反转一整条链的方向，造成的影响也是让链尾 减少 ，链头 增加 ，而链中间的点恰好受到一次 和一次 ， 没有发生变化。此时仍然适用这个结论。

我们考虑另外一种策略：每次在没有染色的节点中，选择 最小的那个进行染色。

我们将证明这样的操作是最优的。下面的证明来自跃迁（QQ：756507076）。

实际上我们只需要证明这个点一定在最优序列的第一个即可。

假设这个点不是第一个，那么其在最终定向之后的图中必然存在来自当前某个黑点的入度，假设当前这个点的入度是 。沿着入边反方向走，找到一条通往一个没有黑点入度的点的路径。此时的代价就是

交换之后是

根据上面发现的结论，我们只需要比较 和 的大小即可。

而 显然是小于 的。根据定义， 是所有点中 最小的，因此 也小于 。

也就是

此时取反这条链不劣。

证毕。

值得一提的是，这个证明并不能推广到图上面，因为该证明不能保证链取反之后是个 DAG（不存在环）。

考虑反转 这一条路径，如果图中又另外存在一条 的路径就会在反转后产生环。

因此取反后的图可能没有合法方案。而树这个结构本身就没有环，因此无论如何都存在一组合法方案。