华为OD机试 - 寻找最富裕的小家庭（Java 2024 C卷 100分）

在这里插入图片描述

华为OD机试 2024C卷题库疯狂收录中，刷题点这里

专栏导读

本专栏收录于《华为OD机试（JAVA）真题（A卷+B卷+C卷）》。

刷的越多，抽中的概率越大，每一题都有详细的答题思路、详细的代码注释、样例测试，发现新题目，随时更新，全天CSDN在线答疑。

一、题目描述

在一棵树中，每个节点代表一个家庭成员，节点的数字表示其个人的财富值，一个节点及其直接相连的子节点被定义为一个小家庭现给你一棵树，请计算出最富裕的小家庭的财富和。

二、输入描述

第一行为一个数N，表示成员总数，成员编号1-N，1<=N<=1000

第二行为N个空格分隔的数，表示编号1- N 的成员的财富值。 0 <= 财富值 <= 1000000

接下来 N-1 行，每行两个空格分隔的整数（N1,N2），表示 N1 是 N2 的父节点。

三、输出描述

最富裕的小家庭的财富和

1、输入

4
100 200 300 500
1 2
1 3
2 4

2、输出

700

3、说明

在这里插入图片描述

四、解题思路

本题的目标是在一个树结构中找到最富裕的小家庭的财富总和。一个小家庭由一个父节点及其直接子节点组成。我们需要构建这棵树，然后遍历每个节点，计算包括该节点本身以及其所有直接子节点的财富总和，最后返回这些总和中的最大值。

步骤如下：

解析输入并构建树：首先读取节点的财富值，并创建树的结构，通常使用邻接表表示。
计算每个小家庭的财富总和：遍历每个节点，累加该节点及其所有直接子节点的财富值。
比较并找出最大的财富和。

五、Java算法源码

public class OdTest01 {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int N = scanner.nextInt();  // 读取成员总数
        int[] wealth = new int[N + 1];  // 用于存储每个成员的财富值，索引从1开始

        // 读取每个成员的财富值
        for (int i = 1; i <= N; i++) {
            wealth[i] = scanner.nextInt();
        }

        // 构建树结构，使用邻接表存储每个节点的子节点
        List<List<Integer>> children = new ArrayList<>();
        for (int i = 0; i <= N; i++) {
            children.add(new ArrayList<>());
        }

        // 读取父子关系，构建树
        for (int i = 1; i < N; i++) {
            int parent = scanner.nextInt();
            int child = scanner.nextInt();
            children.get(parent).add(child);
        }

        // 寻找最富裕的小家庭
        int maxWealth = 0;
        for (int i = 1; i <= N; i++) {
            int familyWealth = wealth[i];  // 小家庭的财富总和起始为父节点的财富值
            // 加上所有直接子节点的财富值
            for (int child : children.get(i)) {
                familyWealth += wealth[child];
            }
            // 更新最大财富和
            if (familyWealth > maxWealth) {
                maxWealth = familyWealth;
            }
        }

        // 输出最大财富和
        System.out.println(maxWealth);
    }
}