day4h专题

牛客国庆集训派对Day4H 树链博弈

题目:点击打开链接 题意:开始题意没弄明白,必须选一个节点变白,然后再选择祖先或者重新选择其他一个节点变白。 分析:结论是如果树的所有层的黑点的个数是偶数,则先手必败。因为全是偶数,先手造作第k层的点后,那么k层的点就变为奇数了(留给后手一个必胜的状态),这时后手也操作k层的一个点,然后复制先手的操作,一定可以留给先手一个全是偶数的状态。这样,一定是后手走完最后一步,先手必败。 代码: #