OJ-0710

示例1

input
4
100 200 300 5001 21 32 4output700

• 100
  • 200
    • 500
  • 300

示例2

input
4
100 200 300 500
1 2
1 3
1 4output1100

• 100
  • 200
  • 500
  • 300

示例3

input
6
100 200 300 400 300 550
1 2
1 3
1 4
2 5
2 6output1050

• 100
  • 200
    • 300
    • 600
  • 300
  • 400

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner scanner = new Scanner(System.in);int N = scanner.nextInt();int[] val = new int[N + 1];for (int i = 1; i <= N; ++i) {val[i] = scanner.nextInt();}Map<Integer, List<Integer>> mp = new HashMap<>();for (int i = 0; i < N - 1; ++i) {int x1 = scanner.nextInt();int x2 = scanner.nextInt();mp.computeIfAbsent(x1, k -> new ArrayList<>()).add(x2);}TreeNode root = new TreeNode(val[1]);for (Map.Entry<Integer, List<Integer>> entry : mp.entrySet()) {TreeNode parent = new TreeNode(val[entry.getKey()]);for (int childId : entry.getValue()) {parent.children.add(new TreeNode(val[childId]));}root.children.add(parent);}int max_wealth = 0;dfs(root, max_wealth);System.out.println(max_wealth);}private static int dfs(TreeNode node, int max_wealth) {int current_wealth = node.value;for (TreeNode child : node.children) {current_wealth += dfs(child, max_wealth);}max_wealth = Math.max(max_wealth, current_wealth);return current_wealth;}
}class TreeNode {int value;List<TreeNode> children;public TreeNode(int value) {this.value = value;this.children = new ArrayList<>();}
}

https://blog.csdn.net/weixin_52908342/article/details/135189680