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

题目描述

在一颗树中，每个节点代表一个家庭成员，节点的数字表示其个人的财富值，一个节点及其直接相连的子节点被定义为一个小家庭。

现给你一颗树，请计算出最富裕的小家庭的财富和。

输入描述

第一行为一个数 N，表示成员总数，成员编号 1~N。1 ≤ N ≤ 1000

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

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

输出描述

最富裕的小家庭的财富和

用例

题目解析

简单的逻辑分析题。

由于题目输入会给出 树形结构 中，父节点->子节点 的信息，比如下面红色部分

4

100 200 300 500

1 21 32 4

因此我们遍历这些信息时，就可以直接将子节点的财富，汇总到其父节点上。

具体实现是，由第二行输入解析得到每个节点的财富值数组 wealth。

然后根据第三行~最后一行的输入：fa ch，执行 wealth[fa] += wealth[ch]，即将子节点的财富值汇总到父节点上。

这样最终wealth数组的最大值就是题解。

需要注意的是，题目规定成员编号 1~N，因此定义wealth数组时，我们应该将其长度定义为N+1，且从索引1开始操作，来匹配成员编号1~N。

2023.11.26 上面逻辑中：

wealth[fa] += wealth[ch]

存在问题。

比如