华为OD机试C卷 - 最富裕的小家庭（ Python C C++ JavaGo JS PHP）

题目描述

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

现在给定一颗树，我们需要计算最富裕的小家庭的财富和。

输入描述

输入包括以下几行：

一个整数N，表示树中家庭成员的总数，1 ≤ N ≤ 1000。
N个由空格分隔的整数，表示每个家庭成员的财富值，-100 ≤ 财富值 ≤ 1000000。
N-1行，每行包含两个由空格分隔的整数（N1, N2），表示N1是N2的父亲。

输出描述

输出一个整数，表示最富裕的小家庭的财富和。

用例

在这里插入图片描述

题目解析

首先，我们需要明确题目要求。题目描述了一个树形结构，每个节点代表一个家庭成员，节点的数字表示其个人的财富值。一个小家庭由一个节点及其直接相连的子节点组成。我们需要计算最富裕的小家庭的财富和。

为了解决这个问题，我们可以使用深度优先搜索（DFS）来遍历树形结构。在DFS过程中，我们可以记录每个小家庭的财富值，并找到最富裕的小家庭。

具体步骤如下：

创建一个字典family，用于记录每个节点的子节点及其财富值。
创建一个字典family_wealth，用于记录每个小家庭的财富值。初始时，将字典中的所有值都设为0。
创建一个变量max_wealth，用于记录最富裕的小家庭的财富值。初始时，将max_wealth设为0。
使用DFS遍历树形结构，对于每个节点：
- 如果当前节点不是叶子节点，则递归遍历其子节点。
- 计算当前小家庭的财富值，并将其存储在family_wealth中。当前小家庭的财富值为当前节点的财富值加上其子节点的财富值之和。
- 如果当前小家庭的财富值大于max_wealth，则更新max_wealth为当前小家庭的财富值。
输出最富裕的小家庭的财富值。

Python代码实现

# 定义一个函数，用于计算小家庭的财富和
def calculate_family_wealth(node, family, family_wealth):
    # 如果当前节点不是叶子节点，则递归遍历其子节点
    if len(family[node]) > 0:
        for child in family[node]:
            calculate_family_wealth(child, family, family_wealth)
    
    # 计算当前小家庭的财富值，并将其存储在 family_wealth 中
    family_wealth[node] = family_wealth.get(node, 0) + family[node][0]
    
    # 更新最富裕的小家庭的财富值
    if family_wealth[node] > max_wealth:
        max_wealth = family_wealth[node]

# 初始化变量和字典
max_wealth = 0  # 最富裕的小家庭的财富值
family = {}  # 记录每个节点的子节点及其财富值
family_wealth = {}  # 记录每个小家庭的财富值

# 读取输入数据
N = int(input().strip())  # 家庭成员的总数
family_wealth[1] = int(input().strip())  # 第一个家庭成员的财富值，也是整个家庭的财富值
family[1] = []  # 第一个家庭成员没有子节点
for i in range(2, N+1):
    node = int(input().strip())  # 当前家庭成员的编号
    wealth = int(input().strip())  # 当前家庭成员的财富值
    parent = int(input().strip())  # 当前家庭成员的父亲编号
    family[node] = []  # 初始化当前家庭成员的子节点列表
    family[parent].append(node)  # 将当前家庭成员添加为其父亲的子节点
    family_wealth[node] = wealth  # 记录当前家庭成员的财富值

# 使用深度优先搜索遍历树形结构，计算最富裕的小家庭的财富和
calculate_family_wealth(1, family, family_wealth)

# 输出最富裕的小家庭的财富和
print(max_wealth)

C代码实现

#include <stdio.h>
#include <stdbool.h> 

int max_wealth; // 定义最大财富
int family[100001][2]; // 定义一个二维数组来存储家族关系
int family_wealth[100001]; // 定义一个数组来存储每个成员的财富

void calculate_family_wealth(int node, int (*family)[2], int *wealth) 
{ // 定义一个函数来计算家族财富
   if (family[node][0] > 0) { // 如果该成员有孩子
       for (int i = 0; i < family[node][0]; i++) { // 遍历该成员的所有孩子
           calculate_family_wealth(family[node][1 + i], family, wealth); // 递归计算每个孩子的财富
       }
   }

   family_wealth[node] = family_wealth[node] + family[node][0]; // 加上该成员的财富

   if (family_wealth[node] > max_wealth) { // 如果该成员的财富比最大财富还要多
       max_wealth = family_wealth[node]; // 更新最大财富
   }
}

int main() {
   int N; // 定义一个变量来存储家族人数
   scanf("%d", &N); // 读取家族人数
   scanf("%d", &family_wealth[1]); // 读取第一个成员的财富
   max_wealth = family_wealth[1]; // 将最大财富初始化为第一个成员的财富

   for (int i = 2; i <= N; i++) 
   { // 遍历家族中的所有成员
       int node, wealth, parent; // 定义三个变量来存储当前成员的信息
       scanf("%d %d %d", &node, &wealth, &parent); // 读取当前成员的信息
       family[node][0] = 0; // 将当前成员的子节点数初始化为0
       family[parent][0]++; // 将父节点的孩子数加1
       family[parent][family[parent][0]++] = node; // 将当前成员添加到父节点的子节点数组中
       family_wealth[node] = wealth; // 将当前成员的财富初始化为输入的财富
   }

   calculate_family_wealth(1, family, family_wealth); // 调用函数计算家族财富

   printf("%d\n", max_wealth); // 输出最大财富

   return 0; // 程序结束
}

C++代码实现

#include <iostream>
#include <vector>

int max_wealth; // 定义最大财富
std::vector<std::vector<int>> family; // 定义一个二维数组来存储家族关系
std::vector<int> family_wealth; // 定义一个数组来存储每个成员的财富

void calculate_family_wealth(int node, const std::vector<std::vector<int>>& family, std::vector<int>& wealth) 
{ // 定义一个函数来计算家族财富
   if (family[node][0] > 0) { // 如果该成员有孩子
       for (int i = 0; i < family[node][0]; i++) { // 遍历该成员的所有孩子
           calculate_family_wealth(family[node][1 + i], family, wealth); // 递归计算每个孩子的财富
       }
   }

   family_wealth[node] = family_wealth[node] + family[node][0]; // 加上该成员的财富

   if (family_wealth[node] > max_wealth) { // 如果该成员的财富比最大财富还要多
       max_wealth = family_wealth[node]; // 更新最大财富
   }
}

int main() {
   int N; // 定义一个变量来存储家族人数
   std::cin >> N; // 读取家族人数
   std::cin >> family_wealth[1]; // 读取第一个成员的财富
   max_wealth = family_wealth[1]; // 将最大财富初始化为第一个成员的财富

   for (int i = 2; i <= N; i++) 
   { // 遍历家族中的所有成员
       int node, wealth, parent; // 定义三个变量来存储当前成员的信息
       std::cin >> node >> wealth >> parent; // 读取当前成员的信息
       family[node].resize(1, 0); // 将当前成员的子节点数初始化为0
       family[parent][0]++; // 将父节点的孩子数加1
       family[parent].push_back(node); // 将当前成员添加到父节点的子节点数组中
       family_wealth[node] = wealth; // 将当前成员的财富初始化为输入的财富
   }

   calculate_family_wealth(1, family, family_wealth); // 调用函数计算家族财富

   std::cout << max_wealth << std::endl; // 输出最大财富

   return 0; // 程序结束
}

Java代码实现

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Main {
    static int max_wealth; // 定义最大财富
    static List<List<Integer>> family; // 定义一个二维数组来存储家族关系
    static List<Integer> family_wealth; // 定义一个数组来存储每个成员的财富

    public static void calculate_family_wealth(int node, List<List<Integer>> family, List<Integer> wealth) 
    { // 定义一个函数来计算家族财富
        if (family.get(node).get(0) > 0) { // 如果该成员有孩子
            for (int i = 0; i < family.get(node).get(0); i++) { // 遍历该成员的所有孩子
                calculate_family_wealth(family.get(node).get(1 + i), family, wealth); // 递归计算每个孩子的财富
            }
        }

        family_wealth.set(node, family_wealth.get(node) + family.get(node).get(0)); // 加上该成员的财富

        if (family_wealth.get(node) > max_wealth) { // 如果该成员的财富比最大财富还要多
            max_wealth = family_wealth.get(node); // 更新最大财富
        }
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int N; // 定义一个变量来存储家族人数
        System.out.println("请输入家族人数：");
        N = scanner.nextInt(); // 读取家族人数
        System.out.println("请输入第一个成员的财富：");
        family_wealth.add(1, scanner.nextInt()); // 读取第一个成员的财富，并将其添加到成员财富列表中
        max_wealth = family_wealth.get(1); // 将最大财富初始化为第一个成员的财富

        for (int i = 2; i <= N; i++) 
        { // 遍历家族中的所有成员
            int node, wealth, parent; // 定义三个变量来存储当前成员的信息
            System.out.println("请输入当前成员的信息：");
            node = scanner.nextInt();
            wealth = scanner.nextInt();
            parent = scanner.nextInt();
            family.add(node, new ArrayList<>()); // 将当前成员添加到家族关系列表中
            family.get(parent).add(node); // 将当前成员添加到父节点的子节点数组中
            family_wealth.add(node, wealth); // 将当前成员的财富初始化为输入的财富
        }

        calculate_family_wealth(1, family, family_wealth); // 调用函数计算家族财富

        System.out.println("最大财富为：" + max_wealth); // 输出最大财富
    }
}

Go代码实现

package main

import (
	"fmt"
	"io"
	"strings"
	"stdio"
)

func main() {
	var maxWealth int
	var family [][]int
	var familyWealth []int

	fmt.Readln(&N) // 读取家族人数
	fmt.Readln(&familyWealth[1]) // 读取第一个成员的财富
	maxWealth = familyWealth[1] // 将最大财富初始化为第一个成员的财富

	for i := 2; i <= N; i++ { // 遍历家族中的所有成员
		var node, wealth, parent int
		fmt.Readln(&node, &wealth, &parent) // 读取当前成员的信息
		family[node] = append(family[node], 0) // 将当前成员的子节点数初始化为0
		family[parent][0]++ // 将父节点的孩子数加1
		family[parent] = append(family[parent], node) // 将当前成员添加到父节点的子节点数组中
		familyWealth[node] = wealth // 将当前成员的财富初始化为输入的财富
	}

	calculateFamilyWealth(1, family, familyWealth) // 调用函数计算家族财富

	fmt.Println(maxWealth) // 输出最大财富
}

func calculateFamilyWealth(node int, family [][]int, familyWealth []int) {
	if family[node][0] > 0 { // 如果该成员有孩子
		for i := 0; i < family[node][0]; i++ { // 遍历该成员的所有孩子
			calculateFamilyWealth(family[node][1+i], family, familyWealth) // 递归计算每个孩子的财富
		}
	}

	familyWealth[node] = familyWealth[node] + family[node][0] // 加上该成员的财富

	if familyWealth[node] > maxWealth { // 如果该成员的财富比最大财富还要多
		maxWealth = familyWealth[node] // 更新最大财富
	}
}

PHP代码实现

<?php

$max_wealth = 0; // 定义最大财富
$family = array(); // 定义一个二维数组来存储家族关系
$family_wealth = array(); // 定义一个数组来存储每个成员的财富

function calculate_family_wealth($node, $family, $wealth) { // 定义一个函数来计算家族财富
    if ($family[$node][0] > 0) { // 如果该成员有孩子
        for ($i = 0; $i < $family[$node][0]; $i++) { // 遍历该成员的所有孩子
            calculate_family_wealth($family[$node][1 + $i], $family, $wealth); // 递归计算每个孩子的财富
        }
    }

    $family_wealth[$node] = $family_wealth[$node] + $family[$node][0]; // 加上该成员的财富

    if ($family_wealth[$node] > $max_wealth) { // 如果该成员的财富比最大财富还要多
        $max_wealth = $family_wealth[$node]; // 更新最大财富
    }
}

public function main() {
    $scanner = new Scanner(STDIN);
    $N = 0; // 定义一个变量来存储家族人数
    echo "请输入家族人数：<br>";
    $N = $scanner->nextInt(); // 读取家族人数
    echo "请输入第一个成员的财富：<br>";
    $family_wealth[] = $scanner->nextInt(); // 读取第一个成员的财富，并将其添加到成员财富列表中
    $max_wealth = $family_wealth[1]; // 将最大财富初始化为第一个成员的财富

    for ($i = 2; $i <= $N; $i++) { // 遍历家族中的所有成员
        $node = 0;
        $wealth = 0;
        $parent = 0;
        echo "请输入当前成员的信息：<br>";
        $node = $scanner->nextInt();
        $wealth = $scanner->nextInt();
        $parent = $scanner->nextInt();
        $family[] = array($node, array()); // 将当前成员添加到家族关系列表中
        $family[$parent][] = $node; // 将当前成员添加到父节点的子节点数组中
        $family_wealth[] = $wealth; // 将当前成员的财富初始化为输入的财富
    }

    calculate_family_wealth(1, $family, $family_wealth); // 调用函数计算家族财富

    echo "最大财富为：" . $max_wealth; // 输出最大财富
}

main();

JS代码实现


const maxWealth = 0; // 定义最大财富
const family = new Array(100001).fill(0).map(() => new Array(2).fill(0)); // 定义一个二维数组来存储家族关系
const familyWealth = new Array(100001).fill(0); // 定义一个数组来存储每个成员的财富

function calculateFamilyWealth(node, family, wealth) { // 定义一个函数来计算家族财富
   if (family[node][0] > 0) { // 如果该成员有孩子
       for (let i = 0; i < family[node][0]; i++) { // 遍历该成员的所有孩子
           calculateFamilyWealth(family[node][1 + i], family, wealth); // 递归计算每个孩子的财富
       }
   }

   familyWealth[node] = familyWealth[node] + family[node][0]; // 加上该成员的财富

   if (familyWealth[node] > maxWealth) { // 如果该成员的财富比最大财富还要多
       maxWealth = familyWealth[node]; // 更新最大财富
   }
}

async function main() {
   const N = parseInt(prompt("请输入家族人数：")); // 读取家族人数
   familyWealth[1] = parseInt(prompt("请输入第一个成员的财富：")); // 读取第一个成员的财富
   maxWealth = familyWealth[1]; // 将最大财富初始化为第一个成员的财富

   for (let i = 2; i <= N; i++) { // 遍历家族中的所有成员
       const node = i; // 定义一个变量来存储当前成员的编号
       const wealth = parseInt(prompt("请输入当前成员的财富：")); // 读取当前成员的财富
       const parent = parseInt(prompt("请输入当前成员的父节点编号：")); // 读取当前成员的父节点编号
       family[parent][0]++; // 将父节点的孩子数加1
       family[parent][family[parent][0]++] = node; // 将当前成员添加到父节点的子节点数组中
       familyWealth[node] = wealth; // 将当前成员的财富初始化为输入的财富
   }

   calculateFamilyWealth(1, family, familyWealth); // 调用函数计算家族财富

   console.log(maxWealth); // 输出最大财富
}
main();