Find Number of Coins to Place in Tree Nodes
You are given an undirected tree with n nodes labeled from 0 to n - 1, and rooted at node 0. You are given a 2D integer array edges of length n - 1, where edges[i] = [ai, bi] indicates that there is an edge between nodes ai and bi in the tree.
You are also given a 0-indexed integer array cost of length n, where cost[i] is the cost assigned to the i^th node.
You need to place some coins on every node of the tree. The number of coins to be placed at node i can be calculated as:
- If size of the subtree of node
iis less than3, place1coin. - Otherwise, place an amount of coins equal to the maximum product of cost values assigned to
3distinct nodes in the subtree of nodei. If this product is negative, place0coins.
Return an array coin of size n such that coin[i] is the number of coins placed at node i.
Example 1
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]For node 0 place 6 * 5 * 4 = 120 coins, and all other nodes are leaves with subtree of size 1, so place 1 coin on each of them.
Example 2
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]Node 0 gets 8 * 7 * 5 = 280 coins, node 1 gets 7 * 5 * 4 = 140 coins, node 2 gets 8 * 2 * 2 = 32 coins, and all other nodes are leaves with subtree of size 1.
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
edgesrepresents a valid tree.
Asked at 1 companies
Practice questions like this out loud in a mock coding interview with a live AI interviewer. First one free.