首页 > 试题广场 >

牛牛的糖果树

[编程题]牛牛的糖果树

热度指数：1004 时间限制：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。

算法知识视频讲解

summer09

实际上这个糖果“树”是1为起点的无向图感觉题目没有说明白

发表于 2025-06-26 14:56:14 回复(1)

C++

Djungelskog2026

#include <bits/stdc++.h>

using namespace std;

struct Edge {

int to;

int next;

};

int n;

vector<int> color, head, father, result;

vector<Edge> tree;

vector<vector<int>> cnt;

void dfs(const int u, const int f) {

int e = head[u];

while (e != -1) {

if (tree[e].to != f) {

dfs(tree[e].to, u);

for (int i = 1; i <= 1000; i++) {

cnt[u][i] += cnt[tree[e].to][i];

}

e = tree[e].next;

}

cnt[u][color[u]]++;

}

int main() {

cin >> n;

color.resize(n + 1);

head.assign(n + 1, -1);

father.resize(n + 1);

result.resize(n + 1);

tree.resize(2*(n - 1));

cnt.assign(n + 1, vector<int>(1001));

for (int i = 1; i <= n; i++) {

cin >> color[i];

}

for (int i = 0; i < n - 1; i++) {

int u, v;

cin >> u >> v;

tree[2*i] = {v, head[u]};

head[u] = 2*i;

tree[2*i+1] = {u, head[v]};

head[v] = 2*i + 1;

}

dfs(1, -1);

for (int i = 1; i <= n; i++) {

const int max_cnt = *max_element(cnt[i].begin(), cnt[i].end());

for (int j = 1; j <= 1000; j++) {

if (cnt[i][j] & 1 && cnt[i][j] != max_cnt) {

result[i] ^= j;

}

cout << *max_element(result.begin(), result.end()) << '\n';

}

发表于 2026-04-28 16:35:05 回复(0)

牛客52113612号

import java.util.*;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {

    // 构建节点的邻接表
    static List<Integer>[] tree;
    // 颜色数组
    static int[] colors;
    // tong[i][j]：i节点的子树中颜色j出现的次数
    static int[][] tong;

    static int ans = 0;     // 异或和
    static int maxColor = 0;

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 节点个数
        int n = in.nextInt();

        tree = new ArrayList[n + 1];
        colors = new int[n + 1];
        tong = new int[n + 1][1001];

        // 初始化邻接表
        for (int i = 1; i <= n; i++) {
            tree[i] = new ArrayList<>();
        }
        // 初始化颜色数组
        for (int i = 1; i <= n; i++) {
            colors[i] = in.nextInt();
            maxColor = Math.max(maxColor, colors[i]);
        }

        // 读取树的边
        for (int i = 1; i < n; i++) {
            int x = in.nextInt();
            int y = in.nextInt();
            tree[x].add(y);
            tree[y].add(x);
        }

        // 从根节点（1）开始dfs
        dfs(1, 0);
        System.out.print(ans);
        in.close();
    }

    public static void dfs(int x, int pre) {
        // 当前节点的颜色个数 +1
        tong[x][colors[x]]++;

        // 遍历以x为根节点的子树
        for (int i : tree[x]) {
            if (i == pre)
                continue;
            dfs(i, x);
            // 合并子节点的统计信息
            for (int j = 1; j <= maxColor; j++) {
                tong[x][j] += tong[i][j];
            }
        }

        // 颜色出现次数最大的
        int max = 0;
        for (int j = 1; j <= maxColor; j++) {
            max = Math.max(max, tong[x][j]);
        }

        // 计算剩余颜色的异或和
        int res = 0;
        for (int k = 1; k <= maxColor; k++) {
            if (tong[x][k] != max) {
                // 颜色个数是偶数时异或值为0，只有个数是奇数时异或和不为0
                if (tong[x][k] % 2 == 1) {
                    res ^= k;
                }
            }
        }
        ans = Math.max(ans, res);
    }
}

发表于 2026-04-02 10:12:21 回复(0)

Atodush

我知道这就是个图上遍历, 但我怎么看不懂这糖果要怎么扔呢?

发表于 2025-10-11 15:59:59 回复(0)

偶就要搞开发

题目哪里提到只能异或奇数？

发表于 2025-09-30 11:15:19 回复(1)

一笑而过2222

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

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

提交观点

问题信息

位运算树京东 dfs

难度：

6条回答 94收藏 1455浏览

牛牛的糖果树

输入描述:

输出描述:

输入

输出

说明

输入

输出

说明

问题信息

热门推荐

相关试题