首页 > 试题广场 >

牛牛的糖果树

[编程题]牛牛的糖果树

热度指数：21 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

牛牛的朋友送了她一棵节点数为 $n$ 的糖果树（1号点为根节点），树上的每个糖果都有一个颜色。

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

输入描述:

第一行一个整数 $n (1\leq n \leq1000)$ 。表示树的节点数量。

第二行 $n$ 个整数 $a_{i} (1 \leq a_{i} \leq 1000)$ ，表示节点i的颜色。

接下来 $n-1$ 行，每行两个整数 $u$ , $v$ 表示节点 $u$ 和节点 $v$ 之间有一条边。

输出描述:

输出仅有一行，一个整数表示她一次能吃到的糖果的颜色的异或和最大值。

示例1

输入

输出

说明

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

示例2

输入

输出

说明

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

算法知识视频讲解

一笑而过2222

牛牛有一棵节点数为n的糖果树（1号点为根节点），每个节点有一个颜色。她每次吃一整个子树的糖果，吃之前会扔掉出现次数最多的颜色（若有多个次数最多的颜色则全部扔掉），只能吃一次。求她能吃到的所有糖果颜色的异或和的最大值（多个同色糖果需多次异或）。输入： - 第一行n(1≤n≤1000) - 第二行n个整数表示各节点颜色 - 接下来n-1行每行两个整数u,v表示边输出：异或和最大值

发表于 2025-06-18 11:01:31 回复(2)