Java || Sort || DFS
\nclass Solution {\n    public long[] placedCoins(int[][] edges, int[] cost) {\n        Map<Integer, List<Integer>> map = new HashMap<>();\n        buildMap(map
```\nclass Solution {\n    public long[] placedCoins(int[][] edges, int[] cost) {\n        Map<Integer, List<Integer>> map = new HashMap<>();\n        buildMap(map, edges);\n        long[] res = new long[cost.length];\n        dfs(map, cost, res, 0, -1);\n        return res;\n    }\n\n    void buildMap(Map<Integer, List<Integer>> map, int[][] edges) {\n        for (int[] edge : edges) {\n            map.putIfAbsent(edge[0], new ArrayList<>());\n            map.putIfAbsent(edge[1], new ArrayList<>());\n            map.get(edge[0]).add(edge[1]);\n            map.get(edge[1]).add(edge[0]);\n        }\n    }\n\n    List<Integer> dfs(Map<Integer, List<Integer>> map, int[] cost, long[] res, int node, int par) {\n        List<Integer> minMax = new ArrayList<>();\n        minMax.add(cost[node]);\n        if (!map.containsKey(node)) {\n            res[node] = 1;\n            return minMax;\n        }\n        List<Integer> childs = map.get(node);\n        for (int child : childs) {\n            if (child == par)\n                continue;\n            List<Integer> childMinMax = dfs(map, cost, res, child, node);\n            minMax.addAll(childMinMax);\n        }\n        int minMaxSize = minMax.size();\n        Collections.sort(minMax);\n        if (minMaxSize < 3) {\n            res[node] = 1;\n            return minMax;\n        }\n        Long min = (long) minMax.get(0) * minMax.get(1);\n        Long max = (long) minMax.get(minMaxSize - 3) * minMax.get(minMaxSize - 2);\n        if (min > max) {\n            res[node] = (long) min * minMax.get(minMaxSize - 1);\n        } else {\n            res[node] = (long) max * minMax.get(minMaxSize - 1);\n        }\n        if (res[node] < 0) {\n            res[node] = 0;\n        }\n        if (minMaxSize < 5)\n            return minMax;\n        return new ArrayList<>() {\n            {\n                add(minMax.get(0));\n                add(minMax.get(1));\n                add(minMax.get(minMaxSize - 3));\n                add(minMax.get(minMaxSize - 2));\n                add(minMax.get(minMaxSize - 1));\n            }\n        };\n    }\n}\n```
[]