Problem E.

又是树上又是反常游戏（misere-game）的，不过和之前的 Goodbye 2024 的这个题一样，都不会进行太深的轮次，所以都不需要用 sg 理论等高级知识 = =。

必胜态：存在一条到必败态的决策。
必败态：所有决策都引向必胜。

我们按照 w 从大到小排序，显然选择最大的 w 决策必败，其次所有更大的 w 都在决策点子树里的状态也必败，反之必胜（后手剩下的决策都引向必胜）。

因此第一问只需要用 dfs 序，看子树里有没有处理过的点即可，最简单的是直接用树状数组每次标记下求个和，也可以求所有更大节点的 lca 看在不在子树里，因为可以基数排序所以后者实际可以 O(n)，标程用了前后缀和看子树外有没有省去了 lca 和树状数组。

第二问难度陡增。。

除了上面的情况，后手要赢，要么没得走，要么必然存在先手还能走的决策，只要从这些决策里选最大的先手走完必然自己不能再走，就可以确保获胜，

所以剩下的必胜态也必须都像第一问里的状态那样，能够一步将死对面。

因此我们可以枚举先手和后手的决策，然后看不存在第三步即可。

但是这样复杂度太高，我们考虑只枚举后手决策，因为按上面的分析第三步可以打包处理，现在只需要检查是否存在合法的先手决策即可。

Posted by xiaodao
Category: 日常