Seventh Mist

Codeforces 457F

题目大意

给定一棵nn个节点的二叉树, 其中每个节点要么是叶子, 要么有两个孩子. 每个叶子有一个权值aia_i. 有两个人在树上博弈. 每个人可以选择一个两个孩子都是叶子的节点xx, 然后将这两个叶子的权值中的一个放到xx上, 之后删去这两个叶子. 并且在本次操作后, xx将成为非叶节点. 现在先手需要最大化根节点最后的权值, 而后手需要最小化这个权值. 假设双方都绝顶聪明, 那么, 最后的权值应该是多少? 1n2501 \le n \le 250, 0ai10000 \le a_i \le 1000, 100100组数据.

分析

不妨先考虑aia_i的取值是0101的情况. 因为如果0101的情况可以做了, 我们就可以二分答案来解决原问题.

下面给出一些约定: 称以它为根的子树中有偶数个非叶节点的节点为even节点, 反之为odd节点.

考虑递归解决整个问题: 如果当前节点是odd, 并且它的两个儿子都是even, 那么我们可以发现, 两个儿子的决策是独立的: 如果A想要切换到另外一棵子树进行决策, 那么B可以同样在另一棵子树上走一步来使A的努力变成徒劳.

但如果两个儿子都是odd, 情况就不一样了: 此时存在一次弃权(skip)的机会, 并且双方都可以使用. 因为如果A想要skip, 那么A可以切换到另外一棵子树上进行操作, 考虑到另外一棵子树是odd, 那么最后必定剩下一步, 这就迫使B在当前子树中再走一步.

我们可以发现: 只有skip次数的奇偶性是我们所需要关注的. 因为如果有偶数次skip, 那么双方可以轮流使用, 抵消掉对方skip的效果.

因此我们记录状态时需要多记录一个量表示当前是否有一次skip机会. 下面按照子树类型和是否有skip机会, 分六种情况讨论:

  1. even-even-noskip, 这是最简单的情况, 我们只需要在noskip的情况下赢得任何一棵子树就可以了;
  2. even-even-canskip, 此时我们只需要凭借canskip赢得一棵子树, 并且对手不能在noskip的情况下赢得另一棵子树;
  3. odd-even-noskip, 此时有两种情况, 第一种是我们能够在noskip的情况下赢得odd, 并且对手不能在noskip的情况下赢得even, 第二种是我们能够在canskip的情况下赢得even, 并且对手不能在canskip的情况下赢得odd, 这里的第二种情况是因为我们在even中走一步之后, (对于对手来说)even就变成了odd, 并且在有两棵odd的时候, 其中一棵对于另外一棵来说就相当于一次skip;
  4. odd-even-canskip, 我们可以把skip看作是odd中的一轮, 因此我们只要能够在canskip的情况下赢得odd, 或者在noskip的情况下赢得even, 我们就赢了;
  5. odd-odd-noskip, 我们只需要在canskip的情况下赢得任何一棵子树就可以了;
  6. odd-odd-canskip, 一种情况是直接用掉这次skip, 否则就需要在有skip的情况下赢得一棵子树, 并且对手在noskip的情况下不能够赢得另外一棵子树.

其实本题还有一些边界情况, 比如说一个叶子节点, 以及一个只剩下一轮的节点的情况. 当我们处理边界的时候, 我们将会遇到一种强制需要使用掉skip的情况, 我们称这种情况为forceskip. 在大部分情况下forceskipcanskip是一样的, 因为弱势的一方大可直接弃疗(这里我还不太懂). 只有少数边界情况的转移不太一样.

那么本题就这么轻松愉快地解决了.