gujju ben ni gamzzat :) 3000<)
Intuition\n Describe your first thoughts on how to solve this problem. \nsauthi pehla to tame question ne samjho ke question ma aevu kidhu 6e ke agar jho subtre
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nsauthi pehla to tame question ne samjho ke question ma aevu kidhu 6e ke agar jho subtree ni size is lesser than 3 then aene 1 coin assign thase or else aena subtree na andar koi pan 3 aeva cost nu combination lo ke jemno product maximum ave...To mane to depth first search ni yaad ave 6e ke aevo node ke jena subtree ma 3 nodes karta ochi values hoi ae to leave athwa aeno just parent j hase... to aena andar calculate kari daiye and then apdo answer ne upar na subtrees mate updation karta jaisuu...to mazza avse...\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\nsauthi pehla to hu graph banavis ...have space bachava mate hu darek node kaya node thi connected 6e aevu darshavis ...ahiya to direction no role nathi atla mate undirected graph j chose karis... atle badhi edges ne src as well as dest no role nibhavvo padse...\n      **HashMap<Integer,List<Integer>> map=new HashMap<>();**\n\n        **for(int i=0;i<edges.length;i++){\n           int src=edges[i][0],dest=edges[i][1];\n            map.putIfAbsent(src, new ArrayList<>());\n            map.putIfAbsent(dest, new ArrayList<>());\n            map.get(src).add(dest);\n            map.get(dest).add(src);\n        }**\n\nmake boolean vis array to track which node is visited and which not...\n\nhave ahiya thi dfs start karis hu mara root thi... \n  **dfs(map,cost,ans,0,vis);**\n\n/// have challo dfs ma \nahiya avine sauthi pehla to photo padoo ke bhai ame to ahiya avela 6e...yaad giri mate...=> and also biji vakht ahiya farithi avva ma time waste na kariye and infinite loop ma na fasai jaiiyeee...\n**vis[curr]=true;**\n\nhave actually ma su 6e ne gunu ke hu darek node pasethi aena best nodes na cost mangis ke je mane best result api sakke...=> **List<Long> temp=new ArrayList<>();**\n\nand aa result na andar aena neighbour na pan cost add on thase and sauthi pehla to aemne j add karvana 6e and then pachi maro potano cost ne hu add karis....and ae neighbor ne kyare visit karvo joie jyare aene pehla thi visit na karyo hoy... agar jo ae pehla thi visited hase then aene kyarek ne kyarek to mara pase pan ayo hase and then maro result calculate karyo hase or else hu j aene bolavu 6e and ae then mane bolavse ...aeva infinite loop ma fasay javase..\n**for(int neigh: map.get(curr)){**\n            **if(!vis[neigh]){**\n                **temp.addAll(dfs(map,cost,ans,neigh,vis));**\n           **}**\n      **}**\n\nhave parki panchayat thai gai hoy then apde potano cost pan add karidejoo \n => **temp.add((long)cost[curr]);**\n...have to actually ma gunu aevu 6e ke mare to maximum product assign karvano 6e to hu to aa array ne sort kari dais and then would calculate the result...=>  **Collections.sort(temp);**\n.....\nhave avi maximum product ni varta to tamara intution pramane to last tran no j maximum product avse ne..... pan na aevu nathi agar to first vada negetive terms thaya and banne negetive terms na mutliplaication na lidhe answer to positive j ayo and then aene last postive number na jode multiplication karyu then ae to tamaro maximum result avse ne....\n\n**if(n>=3){**\n            **long left =  temp.get(0) * temp.get(1);**\n            **long right= temp.get(n-3) * temp.get(n-2);**\n            **ans[curr]=Math.max(0, Math.max(left,right) * temp.get(n-1));**\n        **}**\nelse tamara subtree na andar 3 karta ocha nodes 6e then aeno answer ne set to 1 =>  **else {**\n            **ans[curr]=1L;**\n        **}**\n\n\n//have tamari temp na andar already j 5 node karta ochi values 6e then aene aemne j return karido=> **if(n<=5){return temp;}**\nor else tame tamara temp mathi aevi best possible values ne return karo ..first two and last 3 =>  **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# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\nsimple dfs j approach use kariye 6e then aeno matlab ke ae to  => O(n*log(n)) j thase..\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\ngraph mate : O(n)\nans mate : O(n)\nvis mate : O(n)\ntemp mate : O(1)\n==================\nso overall space complexity is : O(n)\n\n# Code\n```\nclass Solution {\n    public List<Long> dfs(HashMap<Integer,List<Integer>> map,int cost[],long ans[],int curr,boolean vis[]){\n        vis[curr]=true;\n\n        List<Long> temp=new ArrayList<>();\n        for(int neigh: map.get(curr)){\n            if(!vis[neigh]){\n                temp.addAll(dfs(map,cost,ans,neigh,vis));\n            }\n        }\n        temp.add((long)cost[curr]);\n        Collections.sort(temp);\n\n        int n=temp.size();\n        if(n>=3){\n            long left =  temp.get(0) * temp.get(1);\n            long right= 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]=1L;\n        }\n        if(n<=5){return temp;}\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    public long[] placedCoins(int[][] edges, int[] cost) {\n        int n=cost.length;\n        long ans[]=new long[n];\n        HashMap<Integer,List<Integer>> map=new HashMap<>();\n\n        for(int i=0;i<edges.length;i++){\n            int src=edges[i][0],dest=edges[i][1];\n            map.putIfAbsent(src, new ArrayList<>());\n            map.putIfAbsent(dest, new ArrayList<>());\n            map.get(src).add(dest);\n            map.get(dest).add(src);\n        }\n\n        boolean vis[]=new boolean[n];\n\n        dfs(map,cost,ans,0,vis);\n\n        return ans;\n    }\n}\n```
['Java']