AGC010F Tree Game

题意：给出一棵 个节点的树，点有点权。树上的某个节点有一个棋子。

A , B 两人在树上轮流操作， A 先手。

每次操作将棋子所在的点点权减一，然后将棋子移动到相邻的点。

若点权已经为 ，则操作者判负。

对于每个棋子的起始位置，判定是否先手必胜。

，时限 。

---

在博弈题中，分析时常常因为两人相互制约，而可以简化方案。

首先将整棵树黑白染色，先后手都只会走各自的颜色的点。

考虑一类较为简单的情况 ： 菊花图。且棋子初始时在中心。

此时，先手一定将棋子移动到 （点权）最小的分支，而后手只能往回移动。先手必胜等且仅当 。

这能推出，若棋子所在点 周围的点权都 ，则先手必败。

若棋子在点 ，想要从 走向 ，若 ，则后手可以将棋子移动回 ，先手无法越过 。

（若存在先手必胜的策略，那么一定不是硬闯 的 ，因为会被赶回来）

这样，每个点都只能前往权值比自己小的点，转移就变为了 ，容易一次 得到答案。

对于每个点都搜一次即可。复杂度 。