✅Java Easy Solution 🔥with full Explanation🔥Beats 99%
Intuition\n Describe your first thoughts on how to solve this problem. \n#### For every node, we need 2 information\n- number of nodes in the subtree\n- maximum
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n#### For every node, we need 2 information\n- number of nodes in the subtree\n- maximum product using cost of 3 distinct nodes in the subtree. To find this product, we have the following options \n    - Take the largest 3 positive numbers and multiply them.\n    - Take the largest 1 positive & smallest 2 negative numbers & multiply them (since negative * negative = positive)\n\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\nFor every node we return an array of length 6 with the following info about the subtree of that node - \n- Indices 0,1,2 stores the max 3 positive numbers in sorted order.\n- Indices 4,5 stores the smallest 2 negative numbers.\n- Index 3 stores the count of nodes in the subtree.\n\nFor every node, we do the following operations - \n- Make an array max3 of size 6. max3[3]=1 (counting the current node)\n- If cost of current node >= 0, store it in max3[2] (among thepositive numbers), else store it in max3[5](among the least negative numbers). Rest all values will be 0.\n- Iterate through each child of the node. Also check if the child is the parent node, ignore it(since the edges are undirected), else  do the following for each child\n    - Call the function recursively for each child and get the information of their subtree. Lets call the child array as ans.\n    - Add the number of nodes of each subtree in max3[3]. max3[3]+=ans[3].\n    - Compare the indices 0,1,2 in max3 & ans to find the maximum 3 positive numbers among the 6 numbers. store them in max3[0],max3[1],max3[2] in ascending order.\n    -  Compare the indices 4,5 in max3 & ans to find the minimum 2 negative numbers among the 4 numbers. store them in max3[4],max3[5].\n- Now check max3[3]. If the number of nodes <=2 place 1 coin, otherwise - \n    - Multiply 3 largest positive numbers.(max3[0]*max3[1]*max3[2])\n    - Multiply 2 negative & 1 largest positive.(max3[2]*max3[4]*max3[5])\n    - Compare the 2 products and find the max product. Place the same number of coins.\n- Return the max array.\n\n\n# Complexity\n- Time complexity: O(N)\n    - where N is the total number of nodes in the tree\n    - Since the function is called for each node exactly once, complexity is O(n).    \n    - Also note there is a for loop running for all the edges but since its a tree, number of edges = N-1\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: O(h)\n    - where h is the height of the tree\n    - Space required by recursion stack while doing the DFS. \n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass Solution {\n    public long[] placedCoins(int[][] edges, int[] cost) {\n        int n=cost.length;\n        long coins[]=new long[n];\n        List<List<Integer>> adj = new ArrayList<>();\n        for(int i=0;i<n;i++) {\n            adj.add(new ArrayList<>());\n        }\n        for(int i=0;i<edges.length;i++) {\n            adj.get(edges[i][0]).add(edges[i][1]);\n            adj.get(edges[i][1]).add(edges[i][0]);\n        }\n        placeCoins(adj,coins,cost,0, -1);\n        return coins;\n    }\n    int[]placeCoins(List<List<Integer>> adj, long[]coins, int[]cost,int ind, int par) {\n        int[]max3;\n        // store largest 3 positive numbers in the subtree at indices 0,1,2 & smallest negative 2 numbers at indices 4,5.\n        // max product can be formed by largest 3 positive nums or 2 smallest negative & 1 largest.\n        // store number of nodes in subtree at index 3\n        if(cost[ind]>=0) max3 = new int[]{0,0,cost[ind],1, 0,0};\n        else max3 = new int[]{0,0,0,1,0,cost[ind]};\n        for(int child: adj.get(ind)) {\n            if(child==par) continue;\n            int[]ans = placeCoins(adj, coins,cost, child, ind);\n            max3[3]+=ans[3];\n            // find max 3 positive & min 2 negative among the 10 numbers(5 in ans & 5 in max3) & store in max3\n            findAndReplaceMinMax(ans,max3);\n        }\n        if(max3[3]>2) {\n            long prod = (long)max3[0]*(long)max3[1]*(long)max3[2];\n            coins[ind]=prod>0?prod:0;\n            long negProd = (long)max3[2]*(long)max3[4]*(long)max3[5];\n            coins[ind]=negProd>coins[ind]?negProd:coins[ind];\n        }else coins[ind]=1;\n        return max3;\n    }\n\n    void findAndReplaceMinMax(int[]ans, int[]max3) {\n// finding the largest 3 positive numbers\n            for(int i=0;i<3;i++) {\n                if(ans[i]>max3[0]) {\n                    max3[0]=ans[i];\n                    if(max3[0]>max3[1]) {\n                        int temp = max3[1];\n                        max3[1]=max3[0];\n                        max3[0]=temp;\n                        if(max3[1]>max3[2]) {\n                        temp = max3[1];\n                        max3[1]=max3[2];\n                        max3[2]=temp;\n                        }\n                    }\n                }\n            }\n// finding minimum 4 negative numbers\n            for(int i=4;i<6;i++) {\n                if(ans[i]<max3[4]) {\n                    max3[4]=ans[i];\n                    if(max3[5]>max3[4]) {\n                        int temp = max3[5];\n                        max3[5]=max3[4];\n                        max3[4]=temp;\n                    }\n                }\n            }\n\n    }\n}\n```
['Depth-First Search', 'Java']