京东 · 树 · 算法编程题
京东 树 n ≤ 1e4 时限 2 秒 / 256 MB

题目描述

小红有一棵 n 个结点的树，编号为 1 到 n 。小红和朋友想要在树上玩一个游戏，游戏规则如下：
1. 每次删除一个叶子结点，然后将与其相连的边删除。
2. 删除了编号为 x 的结点的人获胜。
小红想知道，如果她先手，她是否能获胜。

输入输出

输入描述
第一行输入一个整数 t ，表示数据组数。
每组数据第一行两个整数 n 和 x ，表示树的结点数和小红想要删除的结点编号。
接下来 n-1 行，每行两个整数 u 和 v ，表示树上存在一条连接 u 和 v 的边。
1 ≤ t ≤ 30
1 ≤ n ≤ 10^4
1 ≤ u, v, x ≤ n
输出描述
输出 t 行，每行一个字符串，如果小红能获胜，输出 win，否则输出 lose。

样例共 1 组

样例 1 · 第一组，3 是叶子结点，可以直接删除
输入
2
5 3
1 2
1 3
2 4
2 5
5 2
1 2
1 3
2 4
2 5
输出
win
lose

算法解析依据充分

考点：树 · 博弈

数据规模 n ≤ 1e4 ｜ 限制 2 秒 / 256MB ｜ 标准输入输出

题目画像

  • 数据规模：n ≤ 1e4，t ≤ 30
  • 复杂度门槛：只允许 O(n log n) 及更优，朴素 O(n²) 会超时。
  • 源站时限：2 秒（牛客口径，非本题专属门槛）

解题思路

推荐方向：树

树结构上的遍历（DFS 求子树信息 / BFS 求层序），多数树题是「后序遍历 + 回溯」。

思路框架（树 通法 · 非本题专属）

  1. 按输入建图（父子关系一般给父节点编号，孩子用邻接表存）。
  2. 确定遍历方式：自底向上合并子树信息（后序 DFS）或自顶向下传参（前序 DFS）。
  3. 对每个节点，用孩子的答案合并出当前节点的答案。
  4. 涉及层间操作（如层序变换）时用 BFS 逐层处理。

实现要点：递归深度可能到 1e5，注意递归爆栈；必要时改迭代或调整递归深度。

复杂度：时间 O(n) ｜ 空间 O(n)

该范式的通法易错点

  • 递归深度过大导致爆栈。
  • 建树时父子关系方向搞反（把树当成有向图但遍历方向错）。

对照本题

  • 数据规模 n ≤ 1e4，只允许 O(n log n) 及更优，朴素 O(n²) 会超时。

样例解读

样例 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 是叶子结点，可以直接删除

解析由校招宝本地引擎整理（依据源站考点标签 / 人工判题标注 / 题面规模信号），非官方题解，仅供思路参考。

本题来源：2023年秋招-京东-技术通用岗位-第六批笔试。

‹ 上一题 全部编程题 下一题 ›
编程算法题为只读内容：无需作答，直接看题与解析 · 本站不提供在线判题 · 解析由校招宝本地引擎整理，非官方题解