AGC017D Game on Tree

题意 ： 有一棵 个节点的树，节点标号为 。

Alice 和 Bob 在这棵树上玩一个游戏，Alice 先手，两人轮流操作：

选择一条树上存在的边，把它断开使树变成两个连通块。然后把不包含 号点的联通块删除

当一个玩家不能操作时输，你需要回答：假如两人都按最优策略操作，谁将获胜。

，时限 。

---

这是一个 的经典题。

若原树中 有 个儿子，则将树复制 份，第 份中保留第 个子树，将其余部分去除。

不难发现，原游戏等价于这一系列新游戏的 和。

考虑如何计算 只有一个儿子的游戏的 值。

若断开和儿子间相连的边，则后继的 值显然为 ，若断开了其他的边，则变为了更小的子问题。

利用数学归纳法不难证明，此时的 值等于以儿子为根的游戏的 值 。

于是只需一次 dfs 即可。

复杂度 。