✅☑[C++/Java/Python/JavaScript] || Beats 100% || EXPLAINED🔥
PLEASE UPVOTE IF IT HELPED\n\n---\n\n\n# Approaches\n(Also explained in the code)\n\n\n\n\n# Complexity\n- Time complexity:\n   O(nlogk)\n    \n\n- Space comple
# PLEASE UPVOTE IF IT HELPED\n\n---\n\n\n# Approaches\n(Also explained in the code)\n\n\n\n\n# Complexity\n- Time complexity:\n   $$O(nlogk)$$\n    \n\n- Space complexity:\n   $$O(n)$$\n    \n\n\n# Code\n```C++ []\nclass Solution {\npublic:\n    // Function to calculate the maximum possible product of coins placed on nodes\n    vector<long long> placedCoins(vector<vector<int>>& edges, vector<int>& cost) {\n        int n = cost.size(); // Number of nodes\n        vector<vector<int>> edge(n); // Adjacency list representation of edges\n        \n        // Creating the graph using the given edges\n        for(auto i : edges){\n            int u = i[0], v = i[1];\n            edge[u].push_back(v);\n            edge[v].push_back(u);\n        }\n\n        // Multisets to store positive and negative costs for each node\n        multiset<int> pos[n];\n        multiset<int, greater<int>> neg[n];\n\n        // Vector to store the final result of coins placed on nodes\n        vector<long long> coins(n);\n\n        // Depth-first search (DFS) function to traverse the graph and calculate coins\n        auto dfs = [&](auto &dfs, int x, int p) -> void {\n            // Inserting costs into respective multisets based on positivity\n            if(cost[x] > 0){\n                pos[x].insert(cost[x]);\n            } else {\n                neg[x].insert(cost[x]);\n            }\n\n            // Recursive DFS traversal for each adjacent node\n            for(auto y : edge[x]){\n                if(y == p) continue; // Skip the parent node\n                dfs(dfs, y, x); // Recursive call for the child node\n\n                // Merging costs from child nodes into current node\n                for(auto i : pos[y]){\n                    pos[x].insert(i);\n                }\n                for(auto i : neg[y]){\n                    neg[x].insert(i);\n                }\n\n                // Trimming the multisets to keep at most 3 elements\n                while((int)pos[x].size() > 3) pos[x].erase(pos[x].begin());\n                while((int)neg[x].size() > 3) neg[x].erase(neg[x].begin());\n            }\n\n            // Counting the number of positive and negative costs\n            int ps = (int)pos[x].size(), ns = (int)neg[x].size();\n\n            // Calculating the maximum product of coins placed on the node\n            if(ps + ns < 3){\n                coins[x] = 1; // Assign 1 coin if less than 3 costs exist\n            } else {\n                long long mx = -9e18; // Initializing the maximum product as a large negative value\n\n                // Calculating maximum product based on different cases of positive and negative costs\n                if(ps >= 3){\n                    auto itr = pos[x].rbegin();\n                    int lst = *itr;\n                    itr++;\n                    int slst = *itr;\n                    itr++;\n                    int tlst = *itr;\n                    mx = max(mx, 1LL * lst * slst * tlst);\n                }\n                if(ns >= 2 && ps >= 1){\n                    auto itr = neg[x].rbegin();\n                    int lst = *itr;\n                    itr++;\n                    int slst = *itr;\n                    int tlst = *pos[x].rbegin();\n                    mx = max(mx, 1LL * lst * slst * tlst);\n                }\n                if(mx > 0){\n                    coins[x] = mx; // Assign the maximum product if positive\n                }\n            }\n        };\n        \n        // Starting DFS from node 0\n        dfs(dfs, 0, -1); // Pass -1 as the parent node (root node)\n\n        return coins; // Return the vector containing coins placed on each node\n    }\n};\n\n\n\n\n```\n\n```Java []\nimport java.util.*;\n\nclass Solution {\n    public long[] placedCoins(int[][] edges, int[] cost) {\n        int n = cost.length;\n        List<List<Integer>> edge = new ArrayList<>(n);\n        for (int i = 0; i < n; i++) {\n            edge.add(new ArrayList<>());\n        }\n\n        for (int[] i : edges) {\n            int u = i[0], v = i[1];\n            edge.get(u).add(v);\n            edge.get(v).add(u);\n        }\n\n        TreeSet<Integer>[] pos = new TreeSet[n];\n        TreeSet<Integer>[] neg = new TreeSet[n];\n\n        for (int i = 0; i < n; i++) {\n            pos[i] = new TreeSet<>();\n            neg[i] = new TreeSet<>(Collections.reverseOrder());\n        }\n\n        long[] coins = new long[n];\n\n        dfs(0, -1, edge, cost, pos, neg, coins);\n\n        return coins;\n    }\n\n    void dfs(int x, int p, List<List<Integer>> edge, int[] cost, TreeSet<Integer>[] pos, TreeSet<Integer>[] neg, long[] coins) {\n        if (cost[x] > 0) {\n            pos[x].add(cost[x]);\n        } else {\n            neg[x].add(cost[x]);\n        }\n\n        for (int y : edge.get(x)) {\n            if (y == p) continue;\n            dfs(y, x, edge, cost, pos, neg, coins);\n\n            pos[x].addAll(pos[y]);\n            neg[x].addAll(neg[y]);\n\n            while (pos[x].size() > 3) pos[x].pollFirst();\n            while (neg[x].size() > 3) neg[x].pollLast();\n        }\n\n        int ps = pos[x].size(), ns = neg[x].size();\n\n        if (ps + ns < 3) {\n            coins[x] = 1;\n        } else {\n            long mx = Long.MIN_VALUE;\n\n            if (ps >= 3) {\n                Iterator<Integer> itr = pos[x].descendingIterator();\n                int lst = itr.next();\n                int slst = itr.next();\n                int tlst = itr.next();\n                mx = Math.max(mx, 1L * lst * slst * tlst);\n            }\n            if (ns >= 2 && ps >= 1) {\n                Iterator<Integer> itr = neg[x].descendingIterator();\n                int lst = itr.next();\n                int slst = itr.next();\n                int tlst = pos[x].last();\n                mx = Math.max(mx, 1L * lst * slst * tlst);\n            }\n            if (mx > 0) {\n                coins[x] = mx;\n            }\n        }\n    }\n}\n\n\n\n```\n```python3 []\n\nclass Solution:\n    def placedCoins(self, edges: List[List[int]], cost: List[int]) -> List[int]:\n        n = len(cost)\n        edge = [[] for _ in range(n)]\n\n        for i in edges:\n            u, v = i[0], i[1]\n            edge[u].append(v)\n            edge[v].append(u)\n\n        pos = [set() for _ in range(n)]\n        neg = [set() for _ in range(n)]\n        coins = [0] * n\n\n        def dfs(x, p):\n            if cost[x] > 0:\n                pos[x].add(cost[x])\n            else:\n                neg[x].add(cost[x])\n\n            for y in edge[x]:\n                if y == p:\n                    continue\n                dfs(y, x)\n\n                pos[x] |= pos[y]\n                neg[x] |= neg[y]\n\n                pos[x] = sorted(pos[x])[:3]\n                neg[x] = sorted(neg[x], reverse=True)[:3]\n\n            ps, ns = len(pos[x]), len(neg[x])\n\n            if ps + ns < 3:\n                coins[x] = 1\n            else:\n                mx = float(\'-inf\')\n\n                if ps >= 3:\n                    lst, slst, tlst = sorted(pos[x])[-3:]\n                    mx = max(mx, lst * slst * tlst)\n\n                if ns >= 2 and ps >= 1:\n                    lst, slst = sorted(neg[x])[:2]\n                    tlst = max(pos[x])\n                    mx = max(mx, lst * slst * tlst)\n\n                if mx > 0:\n                    coins[x] = mx\n\n        dfs(0, -1)\n        return coins\n\n\n```\n```javascript []\nvar placedCoins = function(edges, cost) {\n    const n = cost.length;\n    const edge = Array.from({ length: n }, () => []);\n\n    for (const [u, v] of edges) {\n        edge[u].push(v);\n        edge[v].push(u);\n    }\n\n    const pos = Array.from({ length: n }, () => new Set());\n    const neg = Array.from({ length: n }, () => new Set());\n    const coins = new Array(n).fill(0);\n\n    const dfs = (x, p) => {\n        if (cost[x] > 0) {\n            pos[x].add(cost[x]);\n        } else {\n            neg[x].add(cost[x]);\n        }\n\n        for (const y of edge[x]) {\n            if (y === p) continue;\n            dfs(y, x);\n\n            pos[x] = new Set([...pos[x], ...pos[y]]);\n            neg[x] = new Set([...neg[x], ...neg[y]]);\n\n            pos[x] = Array.from(pos[x]).sort((a, b) => a - b).slice(0, 3);\n            neg[x] = Array.from(neg[x]).sort((a, b) => b - a).slice(0, 3);\n        }\n\n        const ps = pos[x].size, ns = neg[x].size;\n\n        if (ps + ns < 3) {\n            coins[x] = 1;\n        } else {\n            let mx = Number.MIN_SAFE_INTEGER;\n\n            if (ps >= 3) {\n                const [lst, slst, tlst] = Array.from(pos[x]).slice(-3);\n                mx = Math.max(mx, lst * slst * tlst);\n            }\n            if (ns >= 2 && ps >= 1) {\n                const [lst, slst] = Array.from(neg[x]).slice(0, 2);\n                const tlst = Math.max(...Array.from(pos[x]));\n                mx = Math.max(mx, lst * slst * tlst);\n            }\n            if (mx > 0) {\n                coins[x] = mx;\n            }\n        }\n    };\n\n    dfs(0, -1);\n    return coins;\n};\n\n\n\n```\n---\n\n\n\n# PLEASE UPVOTE IF IT HELPED\n\n---\n---\n\n\n---
['Depth-First Search', 'Graph', 'Python', 'C++', 'Java', 'Python3', 'JavaScript']