Simple DFS Solution
Intuition\n Describe your first thoughts on how to solve this problem. \n\nPerform bottom up dfs. Note that the answer for any node which has a subtree with mor
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n\nPerform bottom up dfs. Note that the answer for any node which has a subtree with more than 3 elements in it is the maximum product of cost values assigned to 3 distinct nodes in the subtree. The maximum product will always either be the largest 3 positive numbers in the subtree multiplied together, or the largest positive number and the 2 smallest negative numbers multiplied together. \n\nSo dfs and for each node get the nodes in all of it\u2019s children, which is the current node\u2019s subtree. Then the answer will be the larger of the two products mentioned above. Then return the largest 3 positive values and the smallest 2 negative values so that the current node\u2019s parent node can calculate its answer. In the code we just return the entire list, and since it\'s sorted in reverse we know that the largest 3 positive values will be the first 3 numbers in the list and that the smallest 2 negative numbers will be the last 2 numbers in the list if the list has 2 or more negative numbers. \n\n# Complexity\n- Time complexity: O(n*nlogn) -> You can get a O(n * n) solution if you don\'t sort and use if statements for finding the 3 largest and 2 smallest values\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```cpp []\nclass Solution {\n\npublic:\n    vector<long long>ans; \n    vector<int>cost;\n\n    vector<long long> placedCoins(vector<vector<int>>& edges, vector<int>& cost_) {\n        cost = cost_;\n        ans = vector(cost.size(), -1LL);\n        unordered_map<int, vector<int>>adj_dict; \n        for(auto edge : edges){\n            adj_dict[edge[0]].push_back(edge[1]);\n            adj_dict[edge[1]].push_back(edge[0]);\n        }\n        dfs(0, adj_dict, -1);\n        return ans; \n    }\n\n    vector<long long> dfs(int current_node, unordered_map<int, vector<int>>&adj_dict, int parent){\n        vector<long long> output; \n        output.push_back(cost[current_node]);\n\n        //Base case : leaf node\n        if(adj_dict[current_node].size() == 0){\n            ans[current_node] = 1;\n            return output; \n        }\n\n        //Iterate through all the adjacent nodes except for the parent. Get all of their subtrees and add them to our \n        //list of subtree nodes. Since the answer for each node is the largest possible product of 3 costs in the \n        //subtree of our current node, we only need to keep track of the largest 3 positive value and the smallest\n        //2 negative values. Note that if the product is negative, the answer is 0 in the result per the directions.\n        //Because of this, we only need to keep track of the largest 3 positive costs and the 2 smallest negative costs,\n        //since we can multiply the 2 negative costs and the largest positive cost and still end up with a positive number\n        for(auto child: adj_dict[current_node]){\n            if(child == parent){\n                continue; \n            }\n\n            //Get child subtree result\n            vector<long long> result = dfs(child, adj_dict, current_node);\n\n            //Insert the largest 3 positive values and the 2 smallest negative values into current \n            //node\'s subtree.\n            if(result.size() < 6){\n                for(int i = 0; i<result.size(); ++i){\n                    output.push_back(result[i]);\n                }\n            }else{\n                for(int i = 0; i<3; ++i){\n                    output.push_back(result[i]);\n                }\n                for(int i = 1; i<=2; ++i){\n                    output.push_back(result[result.size()-i]);\n                }\n            }\n        }\n\n        //sort in reverse so that the largest values are in the front\n        //and the smallest values are in the back\n        sort(output.rbegin(), output.rend());\n\n        //if the subtree has less than 3 values, then the answer for the node is 1\n        //per the directions\n        if(output.size() < 3){\n            ans[current_node] = 1;\n            return output; \n        }\n\n        //answer is the product of the largest 3 values or the product of the largest value and the two smallest values\n        long long res_all_pos = output[0] * output[1] * output[2];\n        long long res_2_neg = output[0] * output[output.size()-1] * output[output.size()-2];\n        long long res = max(res_all_pos, res_2_neg);\n        if(res <0){\n            ans[current_node] = 0; \n        }else{\n            ans[current_node]= res; \n        }\n\n        // We can optionally prune our result here if we want\n        /*vector<long long>output2; \n        if(output.size() < 6){\n            output2 = output; \n        }else{\n            output2.push_back(output[0]);\n            output2.push_back(output[1]); \n            output2.push_back(output[2]);\n            output2.push_back(output[output.size()-2]);\n            output2.push_back(output[output.size()-1]);\n        }*/\n        \n        //return largest 3 positive costs and 2 smallest negative costs\n        //so parent can calculate its answer. Here we are just returning the entire list, \n        //but sicne we sort the largest 3 positive will be first 3 numbers, and the smallest\n        //2 negs will be the last two numbers in the list if there are 2 or more negative values\n        //in the list.\n        return output; \n    }\n\n};\n```
['C++']