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

题目描述

小美和小团所在的城市包含N个乡镇，乡镇被编号为1到N并按中心化管理，N个乡镇按层级构成树型关系：即以1号乡镇为中心(根)，对于2号到N号乡镇，i号乡镇的上级乡镇为A[i]号乡镇（1<=A[i]<i），或者说i号乡镇是A[i]号乡镇的一个下属乡镇。每个乡镇只有一个上级乡镇（除了1号乡镇没有上级乡镇）和若干个下属乡镇。
该城市由2(N-1)条单向道路连接各乡镇。除了1号乡镇，每个乡镇都有一条长为1的高速公路通向其上级乡镇，而其上级乡镇则有一条长为2的普通公路通向该乡镇。
现在，小美和小团打算在该城市开展外卖业务。若他们在某个乡镇设立站点，则从该乡镇出发距离不超过2的乡镇都可以享受到他们的外卖服务。那么，他们想知道至少要在多少个乡镇设立站点，才能使所有乡镇都享受到外卖服务。

输入输出

输入描述
第一行输入一个整数T（1<=T<=10），表示数据组数。
每组数据占两行，第一行输入一个整数N（1<=N<=10^5）；
第二行输入N-1个由空格隔开的整数，表示A[2]到A[N]（1<=A[i]<i）。
输出描述
每组数据输出占一行，输出一个整数，表示所需设立的站点数目的最小值。

样例共 1 组

样例 1 · 可以在1号和3号乡镇设立站点。
输入
1
5
1 1 3 3
输出
2

算法解析依据充分

考点：树

数据规模 N ≤ 1e5 ｜ 限制 1 秒 / 256MB ｜ 标准输入输出

题目画像

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

解题思路

推荐方向：树

本题切入点

树上的最小支配集（覆盖距离 2）：按深度从叶子向上贪心放置站点，每次在最远的未覆盖点的祖先处设站。

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

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

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

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

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

该范式的通法易错点

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

对照本题

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

样例解读

样例 1：输入 1 / 5 / 1 1 3 3 → 输出 2

可以在1号和3号乡镇设立站点。

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

本题来源：美团2023校招笔试-编程题（算法编程题）。

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