[HDU-3197] Game

论文题。

题意就是有一棵树，两个玩家轮流进行操作，每次可以删除一条树边，问胜者是先手还是后手。

考虑在树上求 $SG$ 值，假设我们现在处理到子树 $u$，其所有子树的 $SG$ 值已经被维护。注意到每个子树加上其上的一条边其实都是一个独立的游戏，把 $SG$ 值异或起来即可求出该子树的 $SG$ 值。

先给出结论，设子树 $x$ 的 $SG$ 值为 $SG(x)$，则子树 $x$ 加上一条 $x$ 连向父亲的边这一局面的 $SG$ 值为 $SG(x)+1$。

证明：

考虑数学归纳法。

1. 单个结点形成的子树的 $SG=0$（必败），加上一条新边后的 $SG=1$。
2. 若当前已经证完了子树大小 $