寻找最富裕的小家庭 - 华为OD统一考试（C卷）

OD统一考试（C卷）

分值： 100分

题解： Java / Python / C++

题目描述

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

输入描述

第一行为一个数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

输出：
700

示例2

输入：
4
100 200 300 500
1 2
1 3
1 4

输出：
1100

题解

我们可以使用动态规划的思想来解决这个问题。

定义一个数组 f，其中 f[i] 表示与节点 i 直接相连的子节点的财富和。通过遍历输入，将每个子节点的财富值累加到对应的父节点上，得到 f 数组。

最后，遍历整个树的节点，计算每个节点所在小家庭的财富和，取最大值即为最富裕的小家庭的财富和。

Java

import java.util.Scanner;
/**
 * @author code5bug
 */
public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        int n = scanner.nextInt();
        int[] vals = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            vals[i] = scanner.nextInt();
        }

        // f[i] 表示与i直接相连的子节点财富和
        int[] f = new int[n + 1];
        for (int i = 0; i < n - 1; i++) {
            int p = scanner.nextInt();
            int cc = scanner.nextInt();
            f[p] += vals[c];
        }

        int maxsum = 0;
        for (int i = 1; i <= n; i++) {
            // 小家庭的财富和 = 当前节点的财富 + 直接相连的子节点财富和
            maxsum = Math.max(maxsum, vals[i] + f[i]);
        }

        System.out.println(maxsum);
    }
}

Python

n = int(input())
vals = [0] + list(map(int, input().split()))

# f[i] 表示与i直接相连的子节点财富和
f = [0] * (n + 1)

# 构建树的结构并计算子节点财富和
for i in range(n - 1):
    p, c = map(int, input().split())
    f[p] += vals[c]

# 计算每个节点所在小家庭的财富和，取最大值
maxsum = max([vals[i] + f[i] for i in range(1, n + 1)])
print(maxsum)

C++

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<int> vals(n+1, 0);
    for(int i=1;i<=n;i++){
        cin >> vals[i];
    }
	
    // f[i] 表示与i直接相连的子节点财富和
    vector<int> f(n+1, 0);
    int c, p;
    for(int i=0;i<n-1;i++){
        cin >> p >> c;
        f[p] += vals[c];
    }

    int maxsum = 0;
    for(int i=1;i<=n;i++){
        // 小家庭的财富和 = 当前节点的财富 + 直接相连的子节点财富和
        maxsum = max(maxsum, vals[i] + f[i]);
    }
    cout  << maxsum << endl;

}

🙏整理题解不易， 如果有帮助到您，请给点个赞 ‍❤️‍ 和收藏 ⭐，让更多的人看到。🙏🙏🙏