Uoj139 【UER #4】被删除的黑白树

发表于 更新于 分类于 ， ， 阅读次数：

题意：给出一棵 个节点的有根树，定义度数为 的非根节点为叶子。

现在需要把一些节点染成黑色，且使得所有叶节点到根路径上的黑点个数相同。

最大化黑点的个数。

，时限 。

不想搞长剖套路了……

  • 结论 1：若所有的叶节点到根的路径都经过白色节点，那么一定存在另一种更优的染色方案。

    构造：向下 dfs 时碰到白色节点将其染成黑色并停止。

  • 结论 2：若最浅的叶节点到根的路径经过白色节点，那么所有的叶节点到根的路径都经过白色节点。

    证明：所有叶节点与最浅叶节点向上经过的黑点数量相等，路径长度更长，白点只多不少。

  • 结论 3：最优染色方案满足最浅叶节点上方不存在白色节点。

    结合结论 1 和 2，显然。

一个黑点会影响其子树中的所有叶子，若要让黑点尽量多，即需要让黑点的深度尽量大。

设：

  • ：整棵树的最浅叶子深度为 。

  • ： 的子树最浅叶子深度。

  • ： 上方的白点个数。

从上到下考虑，若 ,则必须将当前点染成黑色，否则可以留白。

dfs 即可，复杂度 。