题目描述

小红在和他的朋友博弈，规则如下：给定一棵树，每次可以删除叶子节点，删除编号为x的获胜。问小红能不能获胜。

输入描述

思路:图论 博弈论

解决这个问题的关键在于如何判断是否有可能删除编号为$x$的节点。

我们可以观察到，如果编号为$x$的节点是叶子节点，那么可以直接删除它并获胜。如果编号为$x$的节点不是叶子节点，那么需要通过一系列的操作，使得编号为$x$的节点变成叶子节点，然后删除它。

具体实现时，我们可以首先构建出给定的树，然后检查编号为$x$的节点的度（即它连接的边的数量）。如果它的度小于等于1，那么它是叶子节点，塔子哥可以直接删除它并获胜。如果它的度大于1，那么我们需要检查树的节点数量是否为偶数。如果是偶数，那么有可能通过一系列的操作，使得编号为$x$的节点变成叶子节点，然后删除它。如果是奇数，则无法获胜。

简单证明