Examples

Example 1


![](https://assets.leetcode.com/uploads/2023/11/09/screenshot-2023-11-10-012641.png)

Input: edges = [[0,1],[0,2],[0,3],[0,4],[0,5]], cost = [1,2,3,4,5,6]
Output: [120,1,1,1,1,1]
Explanation: For node 0 place 6 * 5 * 4 = 120 coins. All other nodes are leaves with subtree of size 1, place 1 coin on each of them.

Example 2


![](https://assets.leetcode.com/uploads/2023/11/09/screenshot-2023-11-10-012614.png)

Input: edges = [[0,1],[0,2],[1,3],[1,4],[1,5],[2,6],[2,7],[2,8]], cost = [1,4,2,3,5,7,8,-4,2]
Output: [280,140,32,1,1,1,1,1,1]
Explanation: The coins placed on each node are:
- Place 8 * 7 * 5 = 280 coins on node 0.
- Place 7 * 5 * 4 = 140 coins on node 1.
- Place 8 * 2 * 2 = 32 coins on node 2.
- All other nodes are leaves with subtree of size 1, place 1 coin on each of them.

Example 3


![](https://assets.leetcode.com/uploads/2023/11/09/screenshot-2023-11-10-012513.png)

Input: edges = [[0,1],[0,2]], cost = [1,2,-2]
Output: [0,1,1]
Explanation: Node 1 and 2 are leaves with subtree of size 1, place 1 coin on each of them. For node 0 the only possible product of cost is 2 * 1 * -2 = -4. Hence place 0 coins on node 0.

Constraints

2 <= n <= 2 * 10^4
edges.length == n - 1
edges[i].length == 2
0 <= ai, bi < n
cost.length == n
1 <= |cost[i]| <= 10^4
The input is generated such that edges represents a valid tree.

Solution

Method 1 – DFS with Heap for Top 3 Products

Intuition

For each node, we need to find the maximum product of any 3 costs in its subtree. We can use DFS to collect the top 3 largest and bottom 2 smallest costs in the subtree (to handle negative products). For each node, if the subtree size is less than 3, place 1 coin. Otherwise, compute the maximum product of any 3 costs (either the product of the top 3 largest or the product of the 2 smallest and the largest, to handle negatives). If the product is negative, place 0 coins.

Approach

Build the tree as an adjacency list.
Use DFS to traverse the tree and for each node:
- Collect all costs in the subtree.
- If the subtree size < 3, place 1 coin.
- Otherwise, find the top 3 largest and bottom 2 smallest costs.
- Compute the maximum product of any 3 costs.
- If the product is negative, place 0 coins; else, place product coins.
Return the coins for all nodes.

Code

[{"language":"C++","code":"class Solution {\npublic:\n    vector<int> placedCoins(vector<vector<int>>& edges, vector<int>& cost) {\n        int n = cost.size();\n        vector<vector<int>> g(n);\n        for (auto& e : edges) {\n            g[e[0]].push_back(e[1]);\n            g[e[1]].push_back(e[0]);\n        }\n        vector<int> ans(n);\n        function<vector<int>(int,int)> dfs = [&](int u, int p) -> vector<int> {\n            vector<int> vals = {cost[u]};\n            for (int v : g[u]) if (v != p) {\n                auto sub = dfs(v, u);\n                vals.insert(vals.end(), sub.begin(), sub.end());\n            }\n            if (vals.size() < 3) ans[u] = 1;\n            else {\n                sort(vals.begin(), vals.end());\n                int n = vals.size();\n                long long prod1 = 1LL * vals[n-1] * vals[n-2] * vals[n-3];\n                long long prod2 = 1LL * vals[0] * vals[1] * vals[n-1];\n                long long prod = max(prod1, prod2);\n                ans[u] = prod < 0 ? 0 : prod;\n            }\n            return vals;\n        };\n        dfs(0, -1);\n        return ans;\n    }\n};","lang":"cpp"},{"language"

Related Tags