首页 > 试题广场 >

小红的树上游戏

[编程题]小红的树上游戏
  • 热度指数：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 是叶子结点，可以直接删除
算法知识视频讲解
添加回答
爱唱歌的无尾熊在度假头像 爱唱歌的无尾熊在度假
//若x为叶子直接获胜
//和奇偶性有关,将x变成叶子的人输

//只考虑直连就好了，剩下直连的叶子时就是斩杀线
            //设n个点,e条边,x的度数为d
            //显然可见：无关边数量(e-d),使x变为叶子次数(d-1)
            //先手的出手序号为奇数
            //为了获胜，有奇数==e-d + d-1 + 1(取走x也要一次)
            //偶==n既可
发表于 2025-09-17 20:50:36 回复(0)
提交观点

问题信息

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

热门推荐

相关试题

小红的树上游戏

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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