【华为OD】C卷真题 100分：寻找最富裕的小家庭 C语言代码实现[思路+代码]

C++代码：

【华为OD】C卷真题 100分：寻找最富裕的小家庭 C/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

输出

700 

      879                                                         
                                                            
              +---+                                                          
  3            |   |       ++                               +       +---|   
  |           |   | 3      +                6               +  |   +   |        +
  |      +     |   |       +         +                      +    |  +   |       +
  |      +    |   +---+    +        +        +++++          +   +  +   |        +
  |      +    | +      |   +   +----+        |   |          +   +  +   |        +
  |      +  3 | +      |   +   +    +      2 |   |     2    +   +  +   |        +
  |      +    | +      |   +   +    +        |   |          +   +  +   |        +
  |      +---+ +     |    |  |    +    ----+   |   +---+    |  |  +   |         +
  |      |     +     |    |  |    +    |       |   |   |    |  |  +   |         +
  |    1 |     +     | 8  |  |    +  1 |   |    | 1 |   | 1 |   |  +   |        +
  |      |     +     |    |  |    +    |   |    |   |   |   |   |  +   |        +
  |  +---+     +     +---+   |    ++---+    ++   +---+   +---+   |  +   |        +
  |  |         +         |   |    |         ++              |   |  |+   |        +
  |0 |         +         | 0 |  0 |         ++              | 0 |  |+   |        +
  |  |         +         |   |    |         ++              |   |  |+   |        +
  +---+         +          +-------+                       +---+| +|+   |        +
                +                                                    +   |        +
    0   1   2   3   4   5   6   7   8   9  10  11  12 + v:    w  u m    u 1 0 2 4

题目分析：

        这个按题目逻辑来处理即可，直接将当前父节点下的子节点值汇总到父节点即可，然后找出最大值

代码实现：

#include <stdio.h>
#include <stdlib.h>
 
void bubbleSort(int* arr, int n) {
    int i, j, temp;
    for (i = 0; i < n-1; i++) {
        for (j = 0; j < n-i-1; j++) {
            if (arr[j] > arr[j+1]) {
                temp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = temp;
            }
        }
    }
}
 
int main() {
    int n;
    scanf("%d", &n);
 
    // 动态分配数组
    int* first = (int*)malloc((n+1) * sizeof(int));
    int* second = (int*)malloc((n+1) * sizeof(int));
 
    // 初始化数组
    for (int i = 0; i <= n; i++) {
        first[i] = 0;
        second[i] = 0;
    }
 
    // 读取输入
    for (int i = 1; i <= n; i++) {
        scanf("%d", &first[i]);
        second[i] = first[i];
    }
 
    // 处理边
    for (int i = 0; i < n - 1; i++) {
        int p, s;
        scanf("%d %d", &p, &s);
        second[p] += first[s];
    }
 
    // 排序
    bubbleSort(second, n+1);
 
    // 输出最大值
    printf("%d\n", second[n]);
 
    // 释放内存
    free(first);
    free(second);
 
    return 0;
}