OJ-0710

示例1

input
4
100 200 300 500
 1 2
 1 3
 2 4
 output
 700

• 100
  • 200
    • 500
  • 300

示例2

input
4
100 200 300 500
1 2
1 3
1 4
 output
 1100

• 100
  • 200
  • 500
  • 300

示例3

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

• 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

原文地址：https://blog.csdn.net/wsd_ontheroad/article/details/140337165

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！