Java DFS Solution | Beats 100% Users
 Describe your first thoughts on how to solve this problem.  \n\n# Approach\n\nReturn sorted list of cost for every subtree.\nOne Edge Case would be if we have 
<!-- Describe your first thoughts on how to solve this problem. -->\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\nReturn sorted list of cost for every subtree.\nOne Edge Case would be if we have first 2 negative then pick them because there product would become positive.\n\n<!-- \n# Complexity\n- Time complexity: O(nlogn)\n\n- Space complexity:    \n-->\n\n# Code\n```\nclass Solution {\n    public long[] placedCoins(int[][] edges, int[] cost) {\n        Map<Integer, List<Integer>> map = new HashMap();\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        int n = cost.length;\n        long[] ans = new long[n];\n        Arrays.fill(ans, 0l);\n        boolean[] visited = new boolean[n];\n        dfs(map, cost, ans, 0, visited);\n        return ans;\n    }\n    \n    public List<Integer> dfs(Map<Integer, List<Integer>> map, int[] cost, long[] ans, int curr, boolean[] visited) {\n        \n        visited[curr] = true;\n        \n        List<Integer> temp = new ArrayList();\n        for(int adj: map.get(curr)) {\n            if(!visited[adj])\n                temp.addAll(dfs(map, cost, ans, adj, visited));\n        }\n        temp.add(cost[curr]);\n        Collections.sort(temp);\n        \n        int n = temp.size();\n        if(n >= 3) {\n            // if first 2 are minus pick them\n            long left = (long) temp.get(0) * temp.get(1);\n            long right = (long) temp.get(n-3) * temp.get(n-2);\n            ans[curr] = Math.max(0, Math.max(left, right) * temp.get(n-1));\n        } else {\n            ans[curr] = 1;\n        }\n        \n        if(n <= 5) return temp;\n        \n        return new ArrayList<>(Arrays.asList(temp.get(0), temp.get(1), temp.get(n - 3), temp.get(n - 2), temp.get(n - 1)));\n    }\n}\n```\n\n\n# Subscribe to Our Youtube Channel\nMy coding youtube channel, [cs_iitian](https://www.youtube.com/channel/UCuxmikkhqbmBOUVxf-61hxw), where I explore the fascinating world of programming and tech! \uD83D\uDDA5\uFE0F Join me on this journey of creativity, problem-solving, and continuous learning. Subscribe now and let\'s code together: https://www.youtube.com/channel/UCuxmikkhqbmBOUVxf-61hxw \uD83D\uDD17 Happy coding! \uD83D\uDE80\u2728 #CodingCommunity #TechEnthusiast #LearnToCode
['Java']