在小团的公司中,有n位员工。除了最高领导——小团外,每位员工有且仅有一位直接领导。所以,公司内从属关系可以看成一棵树。 现在,公司接到一个项目,需要重新划分这n位员工的从属关系。新的划分描述如下: 1.每个人要么没有下属,要么有至少两个直接下属(即至少有两人的直接领导为这个人) 2.第i个人的下属(包括自己)有恰好 a_i 个。 请注意,直接下属和下属(包括自己)可分别看做树上点的"儿子"和"子树"。 请问是否存在这么一种关系?注意,输入不会给出最高领导的编号。
输入包含多组数据。 对于每组数据,第一行一个整数n,表示公司有n个人。 接下来一行n个数,第i个数为 a_i ,含义如题面所示。
对每组数据,输出一行"YES"或"NO",代表是否存在这一种从属关系。
3 1 1 3 2 1 2
YES NO
考点:树
限制 1 秒 / 256MB | 标准输入输出
参考方向:树
树结构上的遍历(DFS 求子树信息 / BFS 求层序),多数树题是「后序遍历 + 回溯」。
思路框架(树 通法 · 非本题专属)
实现要点:递归深度可能到 1e5,注意递归爆栈;必要时改迭代或调整递归深度。
复杂度:时间 O(n) | 空间 O(n)
该范式的通法易错点
本题在源数据中没有官方考点标签,方向由题面特征推断,仅供参考。
样例 1:输入 3 / 1 1 3 / 2 / 1 2 → 输出 YES / NO
对于第一组样例,1和2的直接领导均为3即可
对于第二组样例,无法构造出符合题目要求的关系。注意每个有下属的人至少有2个直接下属。
解析由校招宝本地引擎整理(依据源站考点标签 / 人工判题标注 / 题面规模信号),非官方题解,仅供思路参考。
本题来源:美团2023校招技术第5场编程题。