Find Number of Coins to Place in Tree Nodes

Challenge Points: 30

Level: Hard

You are given an undirected tree of n nodes, numbered from 0 to n - 1, with its root at node 0.
The tree structure is provided through an edges list, where each pair [u, v] shows a bidirectional connection between nodes u and v.

Each node i has a cost value given by the array cost.

Your task is to determine how many coins should be placed on each node based on the values found in its entire subtree (including itself):

Rules for coin placement

If a node’s subtree contains fewer than 3 nodes, place 1 coin on that node.
Otherwise:
- Look at all cost values inside that subtree.
- Find the maximum possible product of any 3 distinct cost values.
- If the calculated max product is negative, assign 0 coins.
- Otherwise assign that maximum product as the number of coins.

Return an array coins[] of size n where coins[i] contains the number of coins assigned to node i.

Example 1:

Input: edges = [[0,1],[1,2],[1,3]] cost = [5, -1, 4, 2]

Output: [40, 0, 1, 1]

Explanation:

Node 0 subtree = {0,1,2,3} → values = [5, -1, 4, 2] Best product = 5 × 4 × 2 = 40 → coins[0] = 40 Node 1 subtree = {1,2,3} → values = [-1,4,2] Best product = 4 × 2 × (-1) = -8 → negative → coins[1] = 0, BUT subtree size = 3 so rule applies → place 1 coin Nodes 2 and 3 are leaves → coins = 1