文章目录
- 题目描述
- 输入描述
- 输出描述
- 用例
- 解题思路：
- Java 代码：
- JS 代码：
- Python 代码：
- C 代码：
- C++ 代码：
题目描述
在一颗树中，每个节点代表一个家庭成员，节点的数字表示其个人的财富值，一个节点及其直接相连的子节点被定义为一个小家庭。
现给你一颗树，请计算出最富裕的小家庭的财富和。
输入描述
第一行为一个数 N，表示成员总数，成员编号 1~N。1 ≤ N ≤ 1000
第二行为 N 个空格分隔的数，表示编号 1~N 的成员的财富值。0 ≤ 财富值 ≤ 1000000
接下来 N -1 行，每行两个空格分隔的整数（N1, N2），表示 N1 是 N2 的父节点。
输出描述
最富裕的小家庭的财富和
用例
输入 4
100 200 300 500
1 2
1 3
2 4
输出 700
说明
成员1，2，3 组成的小家庭财富值为600
成员2，4 组成的小家庭财富值为700
解题思路：
- 首先，我们需要构建一个树结构，用于存储家庭成员之间的关系。
- 然后，我们需要遍历树的每个节点，计算以该节点为根的子树的财富和。
- 最后，我们需要找到最大的财富和，即为最富裕的小家庭的财富和。
Java 代码：
import java.util.*;
class FamilyMember {
int id;
int wealth;
List<FamilyMember> children;
public FamilyMember(int id, int wealth) {
this.id = id;
this.wealth = wealth;
this.children = new ArrayList<>();
}
}
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int[] wealths = new int[n + 1];
for (int i = 1; i <= n; i++) {
wealths[i] = sc.nextInt();
}
FamilyMember[] members = new FamilyMember[n + 1];
for (int i = 1; i <= n; i++) {
members[i] = new FamilyMember(i, wealths[i]);
}
for (int i = 1; i < n; i++) {
int parent = sc.nextInt();
int child = sc.nextInt();
members[parent].children.add(members[child]);
}
System.out.println(findMaxWealth(members[1]));
}
public static int findMaxWealth(FamilyMember root) {
int maxWealth = root.wealth;
for (FamilyMember child : root.children) {
maxWealth = Math.max(maxWealth, findMaxWealth(child));
}
return maxWealth;
}
}
JS 代码：
function findMaxWealth(root) {
let maxWealth = root.wealth;
for (let child of root.children) {
maxWealth = Math.max(maxWealth, findMaxWealth(child));
}
return maxWealth;
}
const n = parseInt(readline());
const wealths = readline().split(' ').map(Number);
const members = [];
for (let i = 1; i <= n; i++) {
members[i] = { id: i, wealth: wealths[i - 1], children: [] };
}
for (let i = 1; i < n; i++) {
const [parent, child] = readline().split(' ').map(Number);
members[parent].children.push(members[child]);
}
print(findMaxWealth(members[1]));
Python 代码：
def find_max_wealth(root):
max_wealth = root['wealth']
for child in root['children']:
max_wealth = max(max_wealth, find_max_wealth(child))
return max_wealth
n = int(input())
wealths = list(map(int, input().split()))
members = []
for i in range(1, n + 1):
members.append({'id': i, 'wealth': wealths[i - 1], 'children': []})
for i in range(1, n):
parent, child = map(int, input().split())
members[parent - 1]['children'].append(members[child - 1])
print(find_max_wealth(members[0]))
C 代码：
#include <stdio.h>
#include <stdlib.h>
typedef struct FamilyMember {
int id;
int wealth;
struct FamilyMember** children;
int children_count;
} FamilyMember;
int find_max_wealth(FamilyMember* root) {
int max_wealth = root->wealth;
for (int i = 0; i < root->children_count; i++) {
max_wealth = max(max_wealth, find_max_wealth(root->children[i]));
}
return max_wealth;
}
int main() {
int n;
scanf("%d", &n);
int* wealths = (int*)malloc(n * sizeof(int));
for (int i = 0; i < n; i++) {
scanf("%d", &wealths[i]);
}
FamilyMember** members = (FamilyMember**)malloc((n + 1) * sizeof(FamilyMember*));
for (int i = 1; i <= n; i++) {
members[i] = (FamilyMember*)malloc(sizeof(FamilyMember));
members[i]->id = i;
members[i]->wealth = wealths[i - 1];
members[i]->children = NULL;
members[i]->children_count = 0;
}
for (int i = 1; i < n; i++) {
int parent, child;
scanf("%d %d", &parent, &child);
members[parent]->children_count++;
members[parent]->children = (FamilyMember**)realloc(members[parent]->children, members[parent]->children_count * sizeof(FamilyMember*));
members[parent]->children[members[parent]->children_count - 1] = members[child];
}
printf("%d\n", find_max_wealth(members[1]));
for (int i = 1; i <= n; i++) {
free(members[i]->children);
free(members[i]);
}
free(members);
free(wealths);
return 0;
}
C++ 代码：
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
struct FamilyMember {
int id;
int wealth;
vector<FamilyMember*> children;
};
int find_max_wealth(FamilyMember* root) {
int max_wealth = root->wealth;
for (FamilyMember* child : root->children) {
max_wealth = max(max_wealth, find_max_wealth(child));
}
return max_wealth;
}
int main() {
int n;
cin >> n;
vector<int> wealths(n);
for (int i = 0; i < n; i++) {
cin >> wealths[i];
}
vector<FamilyMember*> members(n + 1);
for (int i = 1; i <= n; i++) {
members[i] = new FamilyMember{i, wealths[i - 1], {}};
}
for (int i = 1; i < n; i++) {
int parent, child;
cin >> parent >> child;
members[parent]->children.push_back(members[child]);
}
cout << find_max_wealth(members[1]) << endl;
for (int i = 1; i <= n; i++) {
delete members[i];
}
return 0;
}
