华为 · 树 · 算法编程题
华为 树 n ≤ 1e5 时限 1 秒 / 256 MB

题目描述

爱丽丝正在森林中布置她的人偶阵列。她将 n 个人偶通过丝线连接成了一棵以人偶 1 为根的树。每个人偶 i 都有一个初始状态 init_i ∈ \0, 1 ，而爱丽丝希望通过魔法将它们全部转变为目标状态 goal_i ∈ \0, 1 。
爱丽丝可以对任意一个人偶 u 施加一次“波及魔法”。该魔法的效果如下：
翻转人偶 u 及其子树中所有与 u 距离为偶数（ 0, 2, 4, ... ）的人偶的状态。所谓翻转，即 0 变为 1 ， 1 变为 0 。
请计算爱丽丝最少需要施加多少次魔法，才能使所有人偶都达到目标状态。

输入输出

输入描述
第一行包含一个整数 n ( 1 ≤ n ≤ 10^5 )，表示人偶的总数。
接下来的 n-1 行，每行包含两个整数 u_i 和 v_i ( 1 ≤ u_i, v_i ≤ n; u_i ≠ v_i )，表示人偶 u_i 与 v_i 之间有一条丝线连接。输入保证这些丝线构成一棵合法的树。
接下来的第 n+1 行包含 n 个整数，第 i 个整数表示人偶 i 的初始状态 init_i ( 0 或 1 )。
接下来的第 n+2 行包含 n 个整数，第 i 个整数表示人偶 i 的目标状态 goal_i ( 0 或 1 )。
输出描述
输出一个整数，表示最少需要的操作次数。

样例共 1 组

样例 1 · 在样例中，树的结构为一条路径 1-2-3-4-5 。 1. 对人偶 1 进行操作：由于人偶 1, 3, 5 与 1 的距离分别为 0, 2, 4 （均为偶数），它们的状态从 0 变为 1 。此时状态序列为 `1 0 1 0 1`。 2. 对人偶 2 进行操作：由于人偶 2, 4 与 2 的距离分别为 0, 2 （均为偶数），它们的状态从 0 变为 1 。此时状态序列为 `1 1 1 1 1`。 总共进行了 2 次操作，满足所有目标状态。
输入
5
1 2
2 3
4 5
3 4
0 0 0 0 0
1 1 1 1 1
输出
2

算法解析依据一般

考点：树

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

题目画像

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

解题思路

参考方向：树

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

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

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

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

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

该范式的通法易错点

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

对照本题

  • 数据规模 n ≤ 1e5，只允许 O(n log n) 及更优，朴素 O(n²) 会超时。
本题在源数据中没有官方考点标签，方向由题面特征推断，仅供参考。

样例解读

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

在样例中，树的结构为一条路径 1-2-3-4-5 。

  1. 对人偶 1 进行操作：由于人偶 1, 3, 5 与 1 的距离分别为 0, 2, 4 （均为偶数），它们的状态从 0 变为 1 。此时状态序列为 1 0 1 0 1。
  2. 对人偶 2 进行操作：由于人偶 2, 4 与 2 的距离分别为 0, 2 （均为偶数），它们的状态从 0 变为 1 。此时状态序列为 1 1 1 1 1。

总共进行了 2 次操作，满足所有目标状态。

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

本题来源：2026年-华为-04月15号开发岗。

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