京东 · 树 · 算法编程题
京东 树 n ≤ 1e3 时限 1 秒 / 256 MB

题目描述

牛牛的朋友送了她一棵节点数为 n 的糖果树（1号点为根节点），树上的每个糖果都有一个颜色。
牛牛吃糖果有一个习惯，她每次都会吃掉一整个子树的糖果，她喜欢与众不同，所以每次吃之前她都会把出现次数最多的颜色的糖果扔掉（可能有多个出现次数最多的颜色，此时要全部扔掉），她可以选择任意一棵子树吃掉，但她只能吃一次，因此他想知道她一次能吃到的所有糖果的颜色的异或和最大是多少（如果吃到了多个颜色相同的糖果，也需要做多次异或），你能帮帮她吗？

输入输出

输入描述
第一行一个整数 n (1≤ n ≤1000) 。表示树的节点数量。
第二行 n 个整数 a_i (1 ≤ a_i ≤ 1000) ，表示节点i的颜色。
接下来 n-1 行，每行两个整数 u , v 表示节点 u 和节点 v 之间有一条边。
输出描述
输出仅有一行，一个整数表示她一次能吃到的糖果的颜色的异或和最大值。

样例共 2 组

样例 1 · 四个节点颜色各不相同。吃掉任意子树都会在吃之前把所有糖果扔掉，因此结果为0。
输入
4
1 2 3 4 
1 2 
2 3 
2 4
输出
0
样例 2 · 吃掉以节点3或节点4为根的子树都只有一个节点，结果都为0，以1为根节点时颜色为1和颜色为2的节点数量都为2，因此结果也为0。吃掉以2为根的子树时节点3和节点4颜色都为2被删除，结果为节点2的颜色1。
输入
4
1 1 2 2 
1 2
2 3 
2 4
输出
1

算法解析依据充分

考点：树 · dfs

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

题目画像

  • 数据规模：n ≤ 1e3
  • 元素值域：a_i ≤ 1e3（注意整数类型选择，避免溢出）
  • 复杂度门槛：允许 O(n²)；若 n ≤ 300，O(n³) 通常也跑得动，需看具体常数。
  • 源站时限：1 秒（牛客口径，非本题专属门槛）

解题思路

推荐方向：树

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

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

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

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

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

该范式的通法易错点

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

对照本题

  • 数据规模 n ≤ 1e3，允许 O(n²)；若 n ≤ 300，O(n³) 通常也跑得动，需看具体常数。
  • 元素值域最大到 1e3 —— 求和 / 相乘时记得开 64 位整数。

样例解读

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

四个节点颜色各不相同。吃掉任意子树都会在吃之前把所有糖果扔掉，因此结果为0。

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

吃掉以节点3或节点4为根的子树都只有一个节点，结果都为0，以1为根节点时颜色为1和颜色为2的节点数量都为2，因此结果也为0。吃掉以2为根的子树时节点3和节点4颜色都为2被删除，结果为节点2的颜色1。

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

本题来源：2024年秋招-京东-后端开发岗-第1批笔试；2024年秋招-京东-算法岗-第1批笔试。

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