C++ | Easy Solution | TC: O(V + E + V log K) | SC: O(V) ⚡⚡
Intuition\nAt each node we only need the greatest 3 positive values of subtree\nand the smallest 3 negative values of subtree of theat node\n\n# Approach\nIf th
# Intuition\nAt each node we only need the greatest 3 positive values of subtree\nand the smallest 3 negative values of subtree of theat node\n\n# Approach\nIf there aren\'t total 3 values whose multiplication is positive \nthen the coins[node] will be zero else will be 1\n\nAt each node we return the greatest 3 positive and smalllest 3 negative values\n\n# Complexity\n- Time complexity:  O(V + E + V log K)\n\n- Space complexity: O(V)\n\n# Code\n```\nclass Solution {\nprivate:\n    vector<vector<long long>> dfsHelper(int node, vector<int>& cost, vector<int>& vis, vector<long long>& coins, vector<int> adj[]){\n\n        vis[node] = 1;\n\n        vector<vector<long long>> p, n;\n        for(auto adjNode: adj[node]){\n            if(!vis[adjNode]){\n                auto it = dfsHelper(adjNode, cost, vis, coins, adj);\n                p.push_back(it[0]);\n                n.push_back(it[1]);\n            }\n        }\n\n        priority_queue<long long, vector<long long>> pos;\n        priority_queue<long long, vector<long long>, greater<long long>> neg;\n        \n        if(cost[node] > 0) pos.push(cost[node]);\n        else    neg.push(cost[node]);\n\n        for(auto itr: p)\n            for(auto it: itr)   pos.push(it);\n        \n        for(auto itr: n)\n            for(auto it: itr)   neg.push(it);\n        \n        int count = 3;\n        vector<long long> topPos, topNeg;\n        while(!pos.empty() && count--){\n            topPos.push_back(pos.top());\n            pos.pop();\n        }\n        count = 3;\n        while(!neg.empty() && count--){\n            topNeg.push_back(neg.top());\n            neg.pop();\n        }\n\n        long long sum1 = 0, sum2 = 0;\n        if(topPos.size() >= 3)  sum1 = topPos[0] * topPos[1] * topPos[2];\n        if(topNeg.size() >= 2 && topPos.size() >= 1)    sum2 = topPos[0] * topNeg[0] * topNeg[1];\n        \n        int m = topPos.size() + topNeg.size();\n        if(m < 3)   coins[node] = 1;\n        else coins[node] =  max(sum1, sum2);\n\n        return {topPos, topNeg};\n    }\npublic:\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 it: edges){\n            int u = it[0], v = it[1];\n            adj[u].push_back(v);\n            adj[v].push_back(u);\n        }\n\n        vector<int> vis(n, 0);\n        vector<long long> coins(n, 0);\n\n        auto it = dfsHelper(0, cost, vis, coins, adj);\n        return coins;\n    }\n};\n\n\n```
['Dynamic Programming', 'Depth-First Search', 'Heap (Priority Queue)', 'C++']