2024年华为OD机试真题-寻找最富裕的小家庭

华为OD机试真题-寻找最富裕的小家庭-2024年OD统一考试（D卷）

题目描述：
在一棵树中，每个节点代表一个家庭成员，节点的数字表示其个人的财富值，一个节点及其直接相连的子节点被定义为一个小家庭。
现给你一棵树，请计算出最富裕的小家庭的财富和。
输入描述：第一行为一个数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
说明：
成员1,2,3组成的小家庭财富值为600
成员2,4组成的小家庭财富值为700
示例2
输入：
4
100 200 300 500
1 2
1 3
1 4
输出：
1100
说明：
成员1,2,3,4组成的小家庭财富值为1100

解题思路：

很简单循环和逻辑判断解题。

Java解法：

import java.util.ArrayList;
import java.util.HashMap;
import java.util.Map.Entry;
import java.util.List;
import java.util.Map;
import java.util.Scanner;
 
public class Main {
  public static void main(String[] args) {
  Scanner in = new Scanner(System.in);
  while (in.hasNextLine()) { /
    int N = Integer.parseInt(in.nextLine());
    String moneys = in.nextLine();
    List<Integer> moneyList = new ArrayList<>();
    for(String money : moneys.split(" ")){
      moneyList.add(Integer.parseInt(money)); 
    }
    
    Map<Integer, List<Integer>> familyMap = new HashMap<>();
    for(int i = 0;i < N-1; i++){
      String line = in.nextLine();
      int parent = Integer.parseInt(line.split(" ")[0]);
      int son = Integer.parseInt(line.split(" ")[1]);
      List<Integer> sons = null;
      if(familyMap.containsKey(parent)){
        sons = familyMap.get(parent);
      } else {
        sons = new ArrayList<>();
      }
      sons.add(son);
      familyMap.put(parent,sons);
    }
    int maxMoney = 0;
    for(Entry<Integer, List<Integer>> entry : familyMap.entrySet()){
      List<Integer> sonList = entry.getValue();
      int parent = entry.getKey();
      int moneyCn = moneyList.get(parent-1);
      for(int son : sonList){
        moneyCn += moneyList.get(son-1);
      }
      if(moneyCn > maxMoney){
        maxMoney = moneyCn;
      }
     }
     System.out.println(maxMoney);
    }
   }
  }

Python解法：

from os import linesep
import sys
 
num = int(sys.stdin.readline().strip())
data = sys.stdin.readline().strip().split(' ')
data = [int(elem) for elem in data]
dependency = {}
while True:
    line = sys.stdin.readline()
    if line == '':
        break
    else:
        relation = line.strip().split(' ')
        if relation[0] in dependency.keys():
            dependency[relation[0]].append(relation[-1])
        else:
            dependency[relation[0]] = [relation[-1]]
 
value = []
for key in dependency.keys():
    value.append(data[int(key)-1])
    for member in dependency[key]:
        value[-1] += data[int(member)-1]
 
if len(value) == 1:
    print(value[-1])
else:
    print(max(value))

C++解法：

#include <cstddef>
#include <iostream>
using namespace std;
#include <map>
#include <vector>
#include <cmath>
 
int main() {
    int N;
    cin >> N;
    vector<int> val(N + 1, 0);
    int i = 0;
    while (i < N) {
        cin >> val[i + 1];
        i++;
    }
    i = 0;
    map<int, vector<int>> mp;
    while (i < N - 1) {
        int x1, x2;
        cin >> x1 >> x2;
        if (mp.find(x1) != mp.end()) {
            mp[x1].push_back(x2);
        } else {
            vector<int> v;
            v.push_back(x2);
            mp.insert(make_pair(x1, v));
        }
        i++;
    }
    int res = 0;
    auto it = mp.begin();
    while (it != mp.end()) {
        int acc = val[it->first];
        for (int i = 0; i < (it->second).size(); i++) {
            acc += val[(it->second)[i]];
        }
        if (res < acc) res = acc;
        it++;
    }
    cout << res << endl;
 
    return 0;
}