🐱‍💻Simple DFS O(N) Solution || Custom Class
Intuition + Approach:\n- We know that we\'ll either use 3 positive numbers, or 2 negative + 1 positive numbers to get the maximum product of 3 numbers.\n- We ke
# Intuition + Approach:\n- We know that we\'ll either use 3 positive numbers, or 2 negative + 1 positive numbers to get the maximum product of 3 numbers.\n- We keep 2 pqs, min-heap to store 3 largest positive, and max-heap to store 2 smallest negative numbers.\n- Then, we simply do a dfs traversal and keep updating our heaps in a post order fashion.\n- Go through the code thoroughly for a better understanding, any doubts would be appreciated in the comments.\n\n\n\n# Code\n```\n#define ll long long\n\nclass largestNumbers{\n    public:\n        priority_queue<int,vector<int>,greater<int>> pos;   //3 largest positive numbers\n        priority_queue<int> neg;                            //2 smallest negative numbers\n        int numNodes;                                       //number of nodes in current subtree\n\n        largestNumbers(){\n            numNodes = 1;\n        }\n\n        void updateSingle(int num){\n            if(num>0){\n                if(pos.size() < 3) pos.push(num);\n                else if(pos.top() < num){\n                    pos.pop();\n                    pos.push(num);\n                }\n            }\n            else{\n                if(neg.size() < 2) neg.push(num);\n                else if(neg.top() > num){\n                    neg.pop();\n                    neg.push(num);\n                }\n            }\n        }\n\n        void update(largestNumbers* ln){\n            auto pn = ln->pos;\n            auto nn = ln->neg;\n            this->numNodes += ln->numNodes;\n            while(!pn.empty()){\n                updateSingle(pn.top());\n                pn.pop();\n            }\n            while(!nn.empty()){\n                updateSingle(nn.top());\n                nn.pop();\n            }\n        }\n\n        ll getProduct(){\n            auto temppos = pos;\n            auto tempneg = neg;\n            ll szp=pos.size(), szn=neg.size();\n            ll lpos=1;\n            ll pp=1, np=1;\n            if(numNodes < 3) return 1;\n\n            while(!pos.empty()){\n                int num=pos.top();\n                pos.pop();\n                lpos=fmax(lpos,num);\n                pp *= num;\n            }\n            while(!neg.empty()){\n                int num=neg.top();\n                neg.pop();\n                np *= num;\n            }\n\n            ll out = 0;\n            if(szp == 3) out=fmax(out, pp);\n            if(szn == 2 && szp >= 1) out=max(out,np*lpos);\n            pos=temppos, neg=tempneg;\n            return out;\n        }\n};\n\nclass Solution {\npublic:\n    vector<ll> coins;\n\n    largestNumbers* helper(vector<int> adj[],vector<int> &cost,int node,int par){\n        largestNumbers* out = new largestNumbers();\n        out->updateSingle(cost[node]);\n\n        for(auto child : adj[node]){\n            if(child == par) continue;\n            largestNumbers* temp=helper(adj,cost,child,node);\n            out->update(temp);\n        }\n\n        ll prod = out->getProduct();\n        coins[node] = prod;\n        return out;\n    }\n\n    vector<long long> placedCoins(vector<vector<int>>& edges, vector<int>& cost) {\n        int n = cost.size();\n\n        vector<int> adj[n];\n        for(auto edge : edges){\n            adj[edge[0]].push_back(edge[1]);\n            adj[edge[1]].push_back(edge[0]);\n        }\n\n        coins.resize(n);\n        helper(adj,cost,0,-1);\n        return coins;\n    }\n};\n```
['C++']