[Greedy] DFS Using Max and Min Heap With Comments
\n\n# Code\n\nclass Solution {\npublic:\n    void helper(int s, vector<int> adj[],vector<int>& visited, vector<int>& cost, vector<long long>& ans, vector<int> m
\n\n# Code\n```\nclass Solution {\npublic:\n    void helper(int s, vector<int> adj[],vector<int>& visited, vector<int>& cost, vector<long long>& ans, vector<int> maximumPerNode[], vector<int> minimumPerNode[]) {\n        visited[s] = 1;\n        // Min heap to track top 3 max elements\n        priority_queue <int, vector<int>, greater<int> > pq; \n        // Max heap to track top 2 min elements\n        priority_queue <int> pq1; \n        pq.push(cost[s]);\n        pq1.push(cost[s]);\n        \n        /**\n         maximumPerNode : It contains top 3 maximum values for each node inside its subtree\n         minimumPerNode : It contains top 2 minimum values for each node inside its subtree\n        **/\n        maximumPerNode[s].push_back(cost[s]);\n        minimumPerNode[s].push_back(cost[s]);\n        \n        for(auto itr: adj[s]) {\n            if(!visited[itr]) {\n                helper(itr, adj, visited, cost, ans, maximumPerNode, minimumPerNode);\n                for(int i = 0; i < maximumPerNode[itr].size(); i++) {\n                    if(pq.size() < 3) {\n                        pq.push(maximumPerNode[itr][i]);\n                    }\n                    else {\n                        if(pq.top() < maximumPerNode[itr][i]) {\n                            pq.pop();\n                            pq.push(maximumPerNode[itr][i]);\n                        }\n                    }\n                } \n\n                for(int i = 0; i < minimumPerNode[itr].size(); i++) {\n                    bool flag = false;\n                    if(pq1.size() < 2) {\n                        pq1.push(minimumPerNode[itr][i]);\n                    }\n                    else {\n                        if(pq1.top() > minimumPerNode[itr][i]) {\n                            pq1.pop();\n                            pq1.push(minimumPerNode[itr][i]);\n                        }\n                    }\n                }\n            }\n        }\n        // Clear the old data pushed initially and construct the new values\n        maximumPerNode[s].clear();\n        minimumPerNode[s].clear();\n        // If queue size is three then we are sure the node \'s\' has atleast 3 nodes in a subtree\n\n        /**\n         For getting the answer for this node we have two options \n         Option 1 : Take 3 maximum values\n         Option 2 : Take 2 minimum values and 1 maximum values since (negative * negative will make the overall product positive)\n        **/\n        if(pq.size() == 3) {\n            long long val = 1LL;\n            long long val1 = 1LL;\n            // Track which element will be considered as the max element for Option 2\n            multiset<int> set1;\n            while(!pq.empty()) {\n                val = (long long) (val * pq.top());\n                set1.insert(pq.top());\n                maximumPerNode[s].push_back(pq.top());\n                pq.pop();\n            }\n\n            while(!pq1.empty()) {\n                auto iterator = set1.find(pq1.top());\n                if(iterator != set1.end()) {\n                    set1.erase(iterator);\n                } \n                val1 = (long long) (val1 * pq1.top());\n                minimumPerNode[s].push_back(pq1.top());\n                pq1.pop();\n            }\n            if(set1.size()) {\n                val1 = (long long)(val1 * (*set1.rbegin()));\n            }\n            if(val1 < 0LL and val < 0LL) ans[s] = 0LL;\n            else ans[s] = max(val, val1);\n        } else {\n            // If size if less than 3 then just update the values for each node\n            while(!pq.empty()) {\n                maximumPerNode[s].push_back(pq.top());\n                pq.pop();\n            }\n            while(!pq1.empty()) {\n                minimumPerNode[s].push_back(pq1.top());\n                pq1.pop();\n            }\n            ans[s] = 1LL;\n        }\n    }\n    vector<long long> placedCoins(vector<vector<int>>& edges, vector<int>& cost) {\n        int n = edges.size();\n        vector<int> adj[n+1];\n        vector<int> maximumPerNode[n+1];\n        vector<int> minimumPerNode[n+1];\n        for(int i = 0; i < edges.size(); i++) {\n            adj[edges[i][0]].push_back(edges[i][1]);\n            adj[edges[i][1]].push_back(edges[i][0]);\n        }\n        vector<long long> ans(n+1);\n        vector<int> visited(n+1);\n        helper(0, adj, visited, cost, ans, maximumPerNode, minimumPerNode);\n        return ans;\n    }\n};\n\n```
['C++']