C++ || DFS
\n# Code\n\nclass Solution {\npublic:\n    vector<long long> ans;\n\n    vector<long long> dfs(int node, vector<vector<int>>& edges, vector<int>& cost, vector<b
\n# Code\n```\nclass Solution {\npublic:\n    vector<long long> ans;\n\n    vector<long long> dfs(int node, vector<vector<int>>& edges, vector<int>& cost, vector<bool>& visited) {\n        priority_queue<int> neg;\n        priority_queue<int, vector<int>, greater<int>> pos;\n\n        visited[node] = true;\n\n        for (auto edge : edges[node]) {\n            if (visited[edge]) continue;\n            vector<long long> search = dfs(edge, edges, cost, visited);\n\n            for (int i = 0; i < 3 && search[i] != 0; i++) {\n                if (pos.size() == 3){\n                    if (search[i] > pos.top()) pos.pop();\n                    else break;\n                }\n                pos.push(search[i]);\n            }\n            for (int i = 3; i < 6 && search[i] != 0; i++) {\n                if (neg.size() == 3) {\n                    if (search[i] < neg.top()) neg.pop();\n                    else break;\n                }\n                neg.push(search[i]);\n            }\n        }\n        //if positive\n        if (cost[node] > 0) {\n            if (pos.size() < 3) pos.push(cost[node]);\n            else if (pos.top() < cost[node]){\n                pos.pop();\n                pos.push(cost[node]);\n            }\n        }\n\n        //if negative\n        else {\n            if (neg.size() < 3) neg.push(cost[node]);\n            else if (neg.top() > cost[node]) {\n                neg.pop();\n                neg.push(cost[node]);\n            }\n        }\n\n        vector<long long> heap(6, 0);\n        for (int i = pos.size()-1; i >= 0; i--) {\n            heap[i] = pos.top();\n            pos.pop();\n        }\n        for (int i = neg.size()-1; i >= 0; i--) {\n            heap[i+3] = neg.top();\n            neg.pop();\n        }\n\n        int num_edges = 0;\n        for (int i = 0; i < 6; i++) \n            if (heap[i] != 0) num_edges++;\n\n        if (num_edges < 3) ans[node] = 1;\n        else {\n            long long rslt = 1;\n            \n            //if all positive exist\n            if (heap[0] != 0 && heap[1] != 0 && heap[2] != 0)\n                rslt = heap[0] * heap[1] * heap[2];\n            //if there is only 2 positives;\n            else if (heap[0] != 0 && heap[1] != 0 && heap[2] == 0) {\n                rslt = heap[0] * heap[1];\n                if (heap[5] != 0) rslt *= heap[5];\n                else if (heap[4] != 0) rslt *= heap[4];\n                else if (heap[3] != 0) rslt *= heap[3];\n            }\n            //if only 1 positive exist\n            else if (heap[0] != 0 && heap[1] == 0) {\n                rslt = heap[0] * heap[3] * heap[4];\n            }\n            //if there is no positives\n            else rslt = heap[3] * heap[4] * heap[5];\n\n            //trying biggest 2 negatives and biggest positive\n            if (heap[0] != 0 && heap[3] != 0 && heap[4] != 0) {\n                long long tmp = heap[0] * heap[3] * heap[4];\n                rslt = max(rslt, tmp);\n            } \n\n            ans[node] = (rslt < 0)? 0 : rslt;\n        }\n\n        return heap;\n    }\n    vector<long long> placedCoins(vector<vector<int>>& edges, vector<int>& cost) {\n        ios_base::sync_with_stdio(false);\n\t\tcin.tie(NULL);\n\t\tcout.tie(NULL);\n\n        int n = cost.size();\n        vector<vector<int>> arr(n, vector<int>(0));\n\n        for (auto edge : edges) {\n            arr[edge[0]].push_back(edge[1]);\n            arr[edge[1]].push_back(edge[0]);\n        }\n\n\n        ans = vector<long long>(n, -1);\n        vector<bool> visited(n, false);\n    \n        dfs(0, arr, cost, visited);\n\n        return ans;\n    }\n};\n```
['Depth-First Search', 'Heap (Priority Queue)', 'C++']