◈ Python ◈ BFS ◈
Intuition/ Approach\n Describe your approach to solving the problem. \n- do a bfs from root node - 0 and store the nodes at a given depth\n- Traverse tree from 
# Intuition/ Approach\n<!-- Describe your approach to solving the problem. -->\n- do a bfs from root node - 0 and store the nodes at a given depth\n- Traverse tree from highest depth to lowest depth \n- At each level/depth , for each node - `node1` on the level/depth calculate:-\n    - `coin` for that node - `node1` base on logic specified in P.S. \n    - Note: We only need smallest two , largest three cost of the subtree rooted at node1 . \n    Call this information `parentInfo[node1] `\n    - append parentsInfo for `parent[node1]`\n\n# Complexity\n- Time complexity: $O(n \\cdot log(n))$\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: $O(n)$\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nfrom collections import defaultdict as dd\nclass Solution:\n    def placedCoins(self, edges: List[List[int]], cost: List[int]) -> List[int]:\n        N=len(cost)\n        nbrs = dd(lambda : dd(lambda : False))\n        all_node_part_of_edge = set()\n        for a,b in edges:\n            nbrs[a][b] = True\n            nbrs[b][a] = True\n            all_node_part_of_edge.add(a)\n            all_node_part_of_edge.add(b)\n        # ###############################################\n        #  do a bfs from root and store the nodes at a given depth\n        # ##############################################\n        periphery = set([0])\n        parent = dd(lambda : None)\n        vis = dd(lambda : False)\n        TREE_DEPTH= 0\n        node_at_depth = dd(lambda : set())\n        while(True):\n            if(len(periphery) == 0 ):\n                break\n            periphery1 = set()\n            TREE_DEPTH+=1\n            for node1 in periphery:\n                vis[node1] = True\n                node_at_depth[TREE_DEPTH].add(node1)\n                for node2 in nbrs[node1]:\n                    if(not(vis[node2] or node2 in periphery)):\n                        periphery1.add(node2)\n                        parent[node2] = node1\n            periphery = periphery1\n\n        # ###########################################\n        # Traverse tree from highest depth to lowest depth \n        # ###########################################\n        # At each level/depth , for each node on the level calculate:-\n        # - coin for that node - node1 base on logic specified in P.S. \n        # - NOte: We only need smallest two , largest three cost of the subtree rooted at node1 . Call this information parentInfo[node1] \n        # - append parentsInfo for parent[node1]\n        # ############################################\n        parentsInfo = dd(lambda : [])\n        coin = dd(lambda : None)\n        depth = TREE_DEPTH\n        while(True):\n            periphery = node_at_depth[depth]\n            if(len(periphery) == 0):\n                break\n            for node1 in periphery:\n                node2 = parent[node1]\n                parentsInfo[node1].append((cost[node1],node1))\n                parentsInfoNode1 = parentsInfo[node1]  \n                costs1 = list(sorted(parentsInfoNode1,key = lambda x: x[0]))\n                # calculate coin for node1\n                _coin = None\n                if(len(costs1)>=5):\n                    # NOte: We only need smallest two , largest three cost of the subtree rooted at node1 to calculate coin[node1]\n                    costs1 = [costs1[0] , costs1[1], costs1[-3], costs1[-2], costs1[-1] ]\n                    x1=   costs1[0][0] * costs1[1][0] * costs1[-1][0]\n                    x2= costs1[-3][0] * costs1[-2][0] * costs1[-1][0]\n                    _coin = max(x1,x2,0)\n                elif(len(costs1)>=4):\n                    # NOte: We only need smallest two , largest three cost of the subtree rooted at node1 to calculate coin[node1]\n                    costs1 = [costs1[0] , costs1[1], costs1[2] , costs1[3]]\n                    \n                    x1=   costs1[0][0] * costs1[1][0] * costs1[-1][0]\n                    x2= costs1[-3][0] * costs1[-2][0] * costs1[-1][0]\n                    _coin = max(x1,x2,0)\n                elif(len(costs1)>=3):\n                    # NOte: We only need smallest two , largest three cost of the subtree rooted at node1 to calculate coin[node1]\n                    costs1 = [costs1[0] , costs1[1], costs1[2] ]\n                    _coin = max(costs1[0][0] * costs1[1][0] * costs1[2][0] , 0)\n                else:\n                    _coin = 1\n                    costs1 = costs1\n                coin[node1] = _coin \n                if(node2 is not None):\n                    # - append parentsInfo for parent[node1]\n                    parentsInfo[node2].extend(costs1)\n            depth+=-1\n        return [coin[i] for i in range(N)]\n            \n\n\n```
['Tree', 'Breadth-First Search', 'Python3']