Simple intuitutive solution for C++
Intuition\n Describe your first thoughts on how to solve this problem. \nTo find the greatest product of three numbers in an array, we need either one of the fo
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nTo find the greatest product of three numbers in an array, we need either one of the following:\n\n    1. Three greatest positive values\n    2. Two greatest negative values and one greatest positive values\n\nGreatest here means the absolute value.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\nEach node will keep a multiset of two values, positive values and negative values. Here values mean the `cost`. This means that when we are making the dfs call, the children will return the same multisets i.e., top 3 positive cost values and top3 negative values. \n\nAdd all these mutilsets into one positive multiset and one negative multiset at each node. Also add the cost value of the current node. This is because the subtree of any node means that the root of the subtree is also included.\n\nNow, the answer will be either product of `top3 positive` or `top2 negative * top1 positive or 0(if negative)`.\n\nAlso, if the size of any multiset is greater than 3, just trim it to the size of 3.\n\n# Code\n```\n#define ll long long\nclass Solution {\n    vector<ll> res;\n    vector<vector<int>> adj;\n    \n    ll calc(vector<multiset<ll>> &st){\n        if(st[0].size()+st[1].size()<3){\n            return 1ll*1;\n        }else{\n            vector<ll> pos(st[0].begin(),st[0].end());\n            vector<ll> neg(st[1].begin(),st[1].end());\n            \n            reverse(pos.begin(),pos.end());\n            reverse(neg.begin(),neg.end());\n            \n            ll all_pos = (pos.size()>=3) ? (pos[0]*pos[1]*pos[2]) : 0;\n            ll one_pos = (pos.size()>=1 and neg.size()>=2) ? (pos[0]*neg[0]*neg[1]) : 0;\n            \n            \n            return max({all_pos,one_pos,1ll*0});\n        }\n    }\n    \n    vector<multiset<ll>> dfs(int src, int par, vector<int> &cost){\n        \n        vector<multiset<ll>> st(2);\n        if(cost[src]>=0){\n            st[0].insert(1ll*cost[src]);\n        }else{\n            st[1].insert(1ll*(-1*cost[src]));\n        }\n        \n        for(int nbr: adj[src]){\n            if(nbr==par)    \n                continue;\n            vector<multiset<ll>> tmp = dfs(nbr,src,cost);\n            for(int i=0;i<2;i++){\n                for(auto &j:tmp[i]){\n                    st[i].insert(j);\n                    if(st[i].size()>3){\n                        st[i].erase(st[i].begin());\n                    }\n                }\n            }\n        }\n        \n        ll ans = calc(st); \n        \n        res[src]=ans;\n        return st;\n    }\npublic:\n    vector<ll> placedCoins(vector<vector<int>>& edges, vector<int>& cost) {\n        int n = cost.size();\n        res = vector<ll>(n,0);\n        adj = vector<vector<int>>(n);\n        for(auto &i:edges){\n            adj[i[0]].push_back(i[1]);\n            adj[i[1]].push_back(i[0]);\n        }\n        \n        \n        dfs(0,-1,cost);\n        \n        return res;\n        \n    }\n};\n```
['C++']