bzoj3722

题意

给定一棵树,除叶子外所有结点儿子数量为奇数;叶子有权值(0,-1,-2),先手将某(0)变成(-1),后手将某(0)变成(-2);对于一种结束状态,每个节点的权值为儿子节点的中位数。求先手是否必胜,如果必胜,问有哪些(0)节点先手第一次操作时将其变成(-1)后还为必胜

做法

对原树进行操作:儿子节点(-1)个数与(-2)相等时,将该节点置为(0);否则置为两数个数较大值
若根为(-1)(0)则必胜

  • (-1)
    先手选择任意(0)叶子均必胜:最多导致根的一个(0)(-1)变成(-2),此时根仍为(-1)(0)
  • (0)
    递归求解,先考虑根,选择(0)儿子;或(-2)儿子(其(1)儿子个数(-1)(1)=其(2)儿子)。
原文地址:https://www.cnblogs.com/Grice/p/12532754.html