首页 > 试题广场 >

小红的树上游戏

[编程题]小红的树上游戏
  • 热度指数：199 时间限制：C/C++ 2秒，其他语言4秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
小红有一棵 n 个结点的树，编号为 1 到 n。小红和朋友想要在树上玩一个游戏，游戏规则如下：
1. 每次删除一个叶子结点，然后将与其相连的边删除。
2. 删除了编号为 x 的结点的人获胜。

小红想知道，如果她先手，她是否能获胜。

输入描述:
第一行输入一个整数 t，表示数据组数。
每组数据第一行两个整数 n 和 x，表示树的结点数和小红想要删除的结点编号。
接下来 n-1 行，每行两个整数 u 和 v，表示树上存在一条连接 u 和 v 的边。
1 \leq t \leq 30
1 \leq n \leq 10^4
1 \leq u, v, x \leq n


输出描述:
输出 t 行，每行一个字符串，如果小红能获胜，输出 win，否则输出 lose。
示例1

输入

2
5 3
1 2
1 3
2 4
2 5
5 2
1 2
1 3
2 4
2 5

输出

win
lose

说明

第一组，3 是叶子结点，可以直接删除
算法知识视频讲解
开通博客
头像 丨阿伟丨
发表于 2025-09-16 14:49:15
题目链接 小红的树上游戏 题目描述 在一棵 个节点的树上进行一个游戏。玩家轮流删除一个叶子节点及其相连的边。删除指定节点 的玩家获胜。给定树的结构和节点 ，判断先手玩家（小红）是否必胜。 解题思路 这是一个典型的公平博弈问题。胜负的关键在于分析游戏的状态和玩家的回合。制胜的关键是操作使得目标节点 展开全文
去ta的博客 赞 (0) 回复(0) 收起

问题信息

树 博弈
难度：
1条回答 203浏览

热门推荐

相关试题

小红的树上游戏

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号