美团 · 树 · 算法编程题
美团 时限 1 秒 / 256 MB

题目描述

在小团的公司中,有n位员工。除了最高领导——小团外,每位员工有且仅有一位直接领导。所以,公司内从属关系可以看成一棵树。
现在,公司接到一个项目,需要重新划分这n位员工的从属关系。新的划分描述如下:
1.每个人要么没有下属,要么有至少两个直接下属(即至少有两人的直接领导为这个人)
2.第i个人的下属(包括自己)有恰好 a_i 个。
请注意,直接下属和下属(包括自己)可分别看做树上点的"儿子"和"子树"。
请问是否存在这么一种关系?注意,输入不会给出最高领导的编号。

输入输出

输入描述
输入包含多组数据。
对于每组数据,第一行一个整数n,表示公司有n个人。
接下来一行n个数,第i个数为 a_i ,含义如题面所示。
输出描述
对每组数据,输出一行"YES"或"NO",代表是否存在这一种从属关系。

样例共 1 组

样例 1 · 对于第一组样例,1和2的直接领导均为3即可 对于第二组样例,无法构造出符合题目要求的关系。注意每个有下属的人至少有2个直接下属。
输入
3
1 1 3
2
1 2
输出
YES
NO

算法解析依据一般

考点:树

限制 1 秒 / 256MB | 标准输入输出

题目画像

  • 源站时限:1 秒(牛客口径,非本题专属门槛)

解题思路

参考方向:树

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

思路框架(树 通法 · 非本题专属)

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

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

复杂度:时间 O(n) | 空间 O(n)

该范式的通法易错点

  • 递归深度过大导致爆栈。
  • 建树时父子关系方向搞反(把树当成有向图但遍历方向错)。
本题在源数据中没有官方考点标签,方向由题面特征推断,仅供参考。

题目给出的提示

  • 直接下属和下属(包括自己)可分别看做树上点的"儿子"和"子树"
  • 输入不会给出最高领导的编号

样例解读

样例 1:输入 3 / 1 1 3 / 2 / 1 2 → 输出 YES / NO

对于第一组样例,1和2的直接领导均为3即可

对于第二组样例,无法构造出符合题目要求的关系。注意每个有下属的人至少有2个直接下属。

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

本题来源:美团2023校招技术第5场编程题。

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