Video Solution | C++ | Heap
Video Solution\n\n# Code\n\nclass Solution {\npublic:\n    vector<long long> dfs(int u, int p, vector<vector<int>> & adj, vector<long long> &placed, vector<int>
# [Video Solution](https://www.youtube.com/watch?v=--WpTjxSviY&t=2s)\n\n# Code\n```\nclass Solution {\npublic:\n    vector<long long> dfs(int u, int p, vector<vector<int>> & adj, vector<long long> &placed, vector<int>& cost){\n        priority_queue<int> max_heap;\n        priority_queue<int, vector<int>, greater<int>> min_heap;\n        max_heap.push(cost[u]);\n        min_heap.push(cost[u]);\n        int nodes = 1;\n        for(auto child: adj[u]){\n            if(child == p) continue;\n            vector<long long> temp = dfs(child, u, adj, placed, cost);\n            for(int i =0; i < temp.size(); i++){\n                max_heap.push(temp[i]);\n                min_heap.push(temp[i]);\n                nodes++;\n            }\n        }\n        long long S1 = min_heap.top(); min_heap.pop();\n        if(nodes == 1){\n            placed[u] = 1;\n            return {cost[u]};\n        }\n        long long S2 = min_heap.top(); min_heap.pop();\n        if(nodes == 2){\n            placed[u] = 1;\n            return {S1, S2};\n        }\n        long long L1 = max_heap.top(); max_heap.pop();\n        if(nodes == 3){\n            placed[u]  = max(S1*S2*L1, 0LL);\n            return {S1, S2, L1};\n        }\n        long long L2 = max_heap.top(); max_heap.pop();\n        long long L3 = max_heap.top(); max_heap.pop();\n        placed[u] = max({L1*L2*L3, S1*S2*L1, 0LL});\n        return {S1, S2, L1, L2, L3};\n    }\n    vector<long long> placedCoins(vector<vector<int>>& edges, vector<int>& cost) {\n        int n = edges.size()+1;\n        vector<vector<int>> adj(n);\n        for(auto e: edges){\n            adj[e[0]].push_back(e[1]);\n            adj[e[1]].push_back(e[0]);\n        }\n        vector<long long> placed(n, 0);\n        dfs(0, -1, adj, placed, cost);\n        return placed;\n    }\n};\n```
['C++']