Beats 90% Clean C++ Solution w/ Detailed Comments
Intuition\n Describe your first thoughts on how to solve this problem. \n\n# Approach\n Describe your approach to solving the problem. \n\n# Complexity\n- Time 
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass Solution {\n    vector<long long> ans;\npublic:\n    // Build Graph and DFS, return lists of costs in subtree including self\n    // Since edges bi-directional, keep track of parent while DFSing to only go downard\n    // This will give us the costs + sizes of all the nodes in current subtree for us to find maxProduct\n\n    // OPTIMIZATION: \n    // - Only return lists of up to size 5\n    // - We only need 2 smallest costs + 3 largest from subtree to get the maxProduct of 3 subCoins\n\n    vector<long long> getBestCostsDFS (const vector<vector<int>>& G,\n              const vector<int>& cost,\n              int currNode,\n              int parent) {\n\n        vector<long long> allCosts = {cost[currNode]};\n\n        // Get costs in subtree, DFS\n        for (const auto child : G[currNode]) {\n            if (child == parent) continue;\n\n            // Get (up to) 5 costs in current child subtree\n            auto subCosts = getBestCostsDFS (G, cost, child, currNode);\n            const int numInSub = subCosts.size();\n            const int numInAll = allCosts.size();\n\n            // Merge current tracking costs with new\n            // If merged array <= size 5, just insert all and sort\n            if (numInSub + allCosts.size() <= 5) {\n                allCosts.insert(allCosts.end(), subCosts.begin(), subCosts.end());\n                std::sort(allCosts.begin(), allCosts.end());\n            } else {\n                // Merge sorted arrays\n                std::vector<long long> temp (5);\n                std::sort(subCosts.begin(), subCosts.end());\n                \n                auto allPtr = 0, subPtr = 0;\n                auto count = 0;\n                // Fill lowest 2\n                while (count < 2) {\n                    if (allPtr >= numInAll) {\n                        temp[count] = subCosts[subPtr];\n                        subPtr++;\n                    } else if (subPtr >= numInSub) {\n                        temp[count] = allCosts[allPtr];\n                        allPtr++;\n                    } else {\n                        temp[count] = allCosts[allPtr] < subCosts[subPtr] ? allCosts[allPtr]:subCosts[subPtr];\n                        allCosts[allPtr] < subCosts[subPtr] ? allPtr++:subPtr++;\n                    }\n                    count++;\n                }\n\n                // Fill Highest 3\n                allPtr = numInAll - 1, subPtr = numInSub - 1;\n                count = 1;\n                while (count <= 3) {\n                    if (allPtr < 0) {\n                        temp[5 - count] = subCosts[subPtr];\n                        subPtr--;\n                    } else if (subPtr < 0) {\n                        temp[5 - count] = allCosts[allPtr];\n                        allPtr--;\n                    } else {\n                        temp[5 - count] = allCosts[allPtr] > subCosts[subPtr] ? allCosts[allPtr]:subCosts[subPtr];\n                        allCosts[allPtr] > subCosts[subPtr] ? allPtr--:subPtr--;\n                    }\n                    count++;\n                }\n\n                allCosts = temp;\n            }\n        } \n\n\n        // Use subtree costs to determine currNode cost\n        // Ans is either:\n        // - 1, if size of subtree < 3\n        // - max product of costs in subtree, which could be (2 negs * 1 pos) or (3 pos)\n        // If max product is negative, set to 0\n        const int numCosts = allCosts.size();\n        if (numCosts < 3) {\n            ans[currNode] = 1;\n        } else {\n            const auto withNegs = allCosts[0] * allCosts[1] * allCosts[numCosts - 1];\n            const auto allPos = allCosts[numCosts - 3] * allCosts[numCosts - 2] * allCosts[numCosts - 1];\n            ans[currNode] = std::max<long long>({0, withNegs, allPos});\n        }\n\n        return allCosts;\n    }\n\n    vector<long long> placedCoins(vector<vector<int>>& edges, vector<int>& cost) {\n        const int n = cost.size();\n        ans.resize(n);\n        vector<vector<int>> G (n);\n\n        for (const auto edge : edges) {\n            const auto a = edge[0];\n            const auto b = edge[1];\n            \n            G[a].push_back(b);\n            G[b].push_back(a);\n        }\n\n        getBestCostsDFS (G, cost, 0, -1);\n\n        return ans;\n    }\n};\n```
['C++']