💻 黄黑树
美团 · 树 · 算法编程题
美团
树
n ≤ 1e5
时限 1 秒 / 256 MB
题目描述
小团作为一名美团骑手，最喜欢的颜色就是黄和黑，因此对包含这两种颜色的事物都格外留意。 这天他发现有一棵树，树上的每个节点都是黄的或者黑的。现在小团想知道对于这棵树中的每个节点，在以其为根的子树中，所有与其颜色不同的节点的深度之和是多少。子树中节点的深度被定义为该节点与该子树根节点之间的最短路径的边数。
输入输出
输入描述
第一行有一个数n，代表这棵树上一共有n个节点，编号为1~n。(1<n<=100000) 第二行有n个数，第i个数表示编号为i的节点的颜色，为0表示黄色，为1表示黑色。 第三行有n-1个数，第i个数表示编号为i+1的节点的父节点编号。
输出描述
在一行中输出n个数，第i个数代表第i个节点的答案。
样例共 1 组
样例 1
输入
10 0 0 1 0 0 1 1 1 0 0 1 2 3 4 4 5 7 6 9
输出
17 13 10 6 3 3 0 0 0 0
算法解析依据一般
考点：树
数据规模 n ≤ 1e5 ｜ 限制 1 秒 / 256MB ｜ 标准输入输出
题目画像
- 数据规模：n ≤ 1e5
- 复杂度门槛：只允许 O(n log n) 及更优，朴素 O(n²) 会超时。
- 源站时限：1 秒（牛客口径，非本题专属门槛）
解题思路
参考方向：树
树结构上的遍历（DFS 求子树信息 / BFS 求层序），多数树题是「后序遍历 + 回溯」。
思路框架（树 通法 · 非本题专属）
- 按输入建图（父子关系一般给父节点编号，孩子用邻接表存）。
- 确定遍历方式：自底向上合并子树信息（后序 DFS）或自顶向下传参（前序 DFS）。
- 对每个节点，用孩子的答案合并出当前节点的答案。
- 涉及层间操作（如层序变换）时用 BFS 逐层处理。
实现要点：递归深度可能到 1e5，注意递归爆栈；必要时改迭代或调整递归深度。
复杂度：时间 O(n) ｜ 空间 O(n)
该范式的通法易错点
- 递归深度过大导致爆栈。
- 建树时父子关系方向搞反（把树当成有向图但遍历方向错）。
对照本题
- 数据规模 n ≤ 1e5，只允许 O(n log n) 及更优，朴素 O(n²) 会超时。
本题在源数据中没有官方考点标签，方向由题面特征推断，仅供参考。
样例
样例 1
- 输入：
10 / 0 0 1 0 0 1 1 1 0 0 / 1 2 3 4 4 5 7 6 9 - 输出：
17 13 10 6 3 3 0 0 0 0
解析由校招宝本地引擎整理（依据源站考点标签 / 人工判题标注 / 题面规模信号），非官方题解，仅供思路参考。
本题来源：美团2023校招笔试-编程题（算法编程题）。
编程算法题为只读内容：无需作答，直接看题与解析 · 本站不提供在线判题 · 解析由校招宝本地引擎整理，非官方题解