526互联

题解 CF457F 【An easy problem about trees】

发布时间 2023-10-09 19:44:07作者: zhaohaikun

尝试理解，感谢 cz_xuyixuan 的题解。

算作是很多情况的补充说明。

我们不妨先二分答案，将 \(\ge mid\) 的设为 \(1\)，\(<mid\) 的设为 \(0\)，于是问题转化为了权值均为 \(0/1\) 的版本。

我们称一棵树的大小为其非叶节点数。

我们称一棵大小为奇数的树为奇树，大小为偶数的树为偶树。

对于奇树有两棵偶子树的情况：最后一次操作由先手完成。我们称，先手能够在当前子树内获胜当且仅当他能在任意一棵子树作为先手内获胜。这是因为如果先手可以在任意一棵子树内获胜，他就可以采取模仿的策略：先在他能赢的子树内操作，如果后手去操作了别的子树，则先手也同样去另一棵子树操作。反之，后手也可以用同样的策略，使得先手在两棵子树内都无法获胜。

对于奇树有两棵奇子树的情况：注意到一棵子树被操作完后，另一棵子树的先后手会发生变化，所以情况就变得更加复杂了，不能单纯地模仿。我们观察其中一棵子树就会发现操作的形式相当于跳过了一次自己的回合，先后手都有这样的机会。

可以发现的是，多次跳过回合是没有意义的，因为对方玩家同样可能进行跳过，而使我方上次的跳过失效，因此，只需要记录是否可以跳过的回合。

于是我们增设状态 \(skip\)：

  • \(=0\)：不能 \(skip\)；
  • \(=1\)：可以 \(skip\)；
  • \(=2\)：先手可以 \(skip\)，若先手不 \(skip\)，后手必须 \(skip\)，详见后文。

于是，我们分情况讨论：

  1. \(skip=0\)：

    1. 奇树有两棵偶子树：先手能获胜当且仅当在任意一个子树内的 \(skip=0\) 能获胜；

    2. 奇树有两棵奇子树：先手能获胜当且仅当在任意一个子树内的 \(skip=1\) 能获胜；

    3. 偶树：显然有一个奇子树和一个偶子树。我们不妨枚举先手的第一步操作：

      1. 操作奇树，那么对于后手相当于情况 1.1。所以，先手能获胜当且仅当先手能奇树中 \(skip=0\) 获胜，并且后手不能在偶树中 \(skip=0\) 获胜；
      2. 操作偶树，那么对于后手相当于情况 1.2。所以，先手能获胜当且仅当先手能偶树中 \(skip=1\) 获胜，并且后手不能在奇树中 \(skip=1\) 获胜。

      先手可以选择操作。

  2. \(skip=1\)：

    先手首先可以考虑 \(skip\)，若后手不能在剩余局面中获胜，则先手获胜。

    注：这里我还不会证明若后手不 \(skip\)，则先手一定会 \(skip\) 来获得子树内的最后一次操作的权利。感性理解下，感觉很有道理。

    1. 偶树：我们声称若后手不 \(skip\)，则先手一定会 \(skip\) 来获得子树内的最后一次操作的权利。那么，先手有如下两种操作：

      1. 先手如果可以在偶树中 \(skip=0\) 获胜，则先手必胜。这是因为先手可以不停地在偶树中操作，那后手有两种可能：

        1. 操作了奇树，先手选择 \(skip\)；
        2. \(skip\) 了。

        上述两种情况都变成了情况 1.1，先手只需要模仿即可。

      2. 先手如果可以在奇树中 \(skip=1\) 获胜，则先手必胜。这是因为先手可以不停地在奇树中操作，那后手有两种可能：

        1. 操作了偶树，则先手选择 \(skip\)；
        2. \(skip\) 了。

        上述两种情况都变成了情况 1.1，先手只需要模仿即可。

        不过，先手也可以选择在操作奇树的时候 \(skip\)，所以是 \(skip=1\)。

        不过有个特例：假设偶树的大小为 \(0\)，则后手可以不选择操作偶树，所以，左子树就变成了 \(skip=2\) 的情况。

    2. 奇树有两棵偶子树：我们枚举先手的第一次操作，于是对于后手就变成了 2.1 的局面。
    3. 奇树有两棵奇子树：我们枚举先手的第一次操作，于是对于后手就变成了 2.1 的局面。

  3. \(skip=2\)：

基本和 \(skip=1\) 类似。

  1. 偶树：根据状态定义，双方必定会有一方 \(skip\)，所以先手一定会获得子树内的最后一次操作的权利。那么，先手有如下两种操作：

    1. 先手如果可以在偶树中 \(skip=0\) 获胜，则先手必胜。这是因为先手可以不停地在偶树中操作，那后手有两种可能：

      1. 操作了奇树，先手选择 \(skip\)；
      2. \(skip\) 了。

      上述两种情况都变成了情况 1.1，先手只需要模仿即可。

    2. 先手如果可以在奇树中 \(skip=1\) 获胜，则先手必胜。这是因为先手可以不停地在奇树中操作，那后手有两种可能：

      1. 操作了偶树，则先手选择 \(skip\)；
      2. \(skip\) 了。

      上述两种情况都变成了情况 1.1，先手只需要模仿即可。

      不过，先手也可以选择在操作奇树的时候 \(skip\)，所以是 \(skip=1\)。

      这种情况不需要分偶树大小为 \(0\) 讨论，因为根据状态定义，若先手不 \(skip\)，后手必须 \(skip\)。

      所以只需要执行 \(skip=1\) 即可。

  2. 奇树有两棵偶子树：我们枚举先手的第一次操作，于是对于后手就变成了 3.1 的局面。

  3. 奇树有两棵奇子树：我们枚举先手的第一次操作，于是对于后手就变成了 3.1 的局面。

时间复杂度 \(O(n\log a)\)。

不过，我们可以把状态记成 \(\min/\max\) 从而避免二分。

时间复杂度 \(O(n)\)。

记录。