Have a look at this shit mess of a code I wrote during contest :((
Code\n\n#define ll long long\n#define pq1 priority_queue<int>\n#define pq2 priority_queue<int, vector<int>, greater<int>>\nclass Solution {\npublic:\n    vector
# Code\n```\n#define ll long long\n#define pq1 priority_queue<int>\n#define pq2 priority_queue<int, vector<int>, greater<int>>\nclass Solution {\npublic:\n    vector<ll> ans;\n    \n    struct Node {\n        priority_queue<int> negative; //maxheap (remove maxm elements)\n        priority_queue<int, vector<int>, greater<int>> positive;\n    };\n\n    struct Node solve (vector<vector<int>>& tree, vector<int>& cost, int i, int parent) {\n        pq1 neg; pq2 pos;\n        for (int &x: tree[i]) {\n            if (x==parent) continue;\n            struct Node temp = solve (tree,cost,x,i);\n            pq1 tempneg = temp.negative; pq2 temppos = temp.positive;\n            while (!tempneg.empty()) {\n                int x = tempneg.top();\n                tempneg.pop();\n                neg.push(x);\n            }\n            while (!temppos.empty()) {\n                int x = temppos.top();\n                temppos.pop();\n                pos.push(x);\n            }\n            while (pos.size()>3) pos.pop();\n            while (neg.size()>3) neg.pop();\n        }\n        int x = cost[i];\n        if (x>=0) pos.push(x);\n        else neg.push(x);\n            while (pos.size()>3) pos.pop();\n            while (neg.size()>3) neg.pop();\n        \n        struct Node ret;\n        ret.positive = pos;\n        ret.negative = neg;\n        if (pos.size()+neg.size()<3){ ans[i] = 1; return ret;}\n        ll maxm = LLONG_MIN;\n\n        int a=-1,b=-1,c=-1,d=1,e=1,f=1;\n        vector<int> posii, negii;\n        while (pos.size()) {\n            int x = pos.top();\n            posii.push_back(x);\n            if (a==-1) a = x;\n            else if (b==-1) b = x;\n            else c = x; //highest\n            pos.pop();\n        }\n        while (neg.size()) {\n            int x = neg.top();\n            negii.push_back(x);\n            if (d==1) d = x;\n            else if (e==1) e = x;\n            else f = x; //most negatve\n            neg.pop();\n        }\n        sort(posii.rbegin(), posii.rend());\n        sort(negii.begin(), negii.end());\n        if (posii.size()>=3) maxm = max (maxm, 1ll*posii[0]*posii[1]*posii[2]);\n        if (negii.size()>=2 && posii.size()>=1) maxm = max (maxm, 1ll*posii[0]*negii[0]*negii[1]);\n        if (negii.size()>=3) maxm = max (maxm, 1ll*negii[2]*negii[0]*negii[1]);\n        for (int &x: posii) pos.push(x);\n        for (int &x: negii) neg.push(x);\n        if (maxm<0) ans[i] = 0;\n        else ans[i] = maxm;\n        return ret;\n    }\n    \n    \n    vector<long long> placedCoins(vector<vector<int>>& edges, vector<int>& cost) {\n        ll n = cost.size();\n        ans.resize(n, 0);\n        vector<vector<int>> tree (n);\n        for (auto &v: edges) {\n            tree[v[0]].push_back(v[1]);\n            tree[v[1]].push_back(v[0]);\n        }\n        solve (tree,cost,0,-1);\n        return ans;\n    }\n};\n```
['C++']