2973. Find Number of Coins to Place in Tree Nodes Hard

1/**
2 * [2973] Find Number of Coins to Place in Tree Nodes
3 *
4 * 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.
5 * 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.
6 * 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:
7 * 
8 * 	If size of the subtree of node i is less than 3, place 1 coin.
9 * 	Otherwise, place an amount of coins equal to the maximum product of cost values assigned to 3 distinct nodes in the subtree of node i. If this product is negative, place 0 coins.
10 * 
11 * Return an array coin of size n such that coin[i] is the number of coins placed at node i.
12 *  
13 * <strong class="example">Example 1:
14 * <img alt="" src="https://assets.leetcode.com/uploads/2023/11/09/screenshot-2023-11-10-012641.png" style="width: 600px; height: 233px;" />
15 * Input: edges = [[0,1],[0,2],[0,3],[0,4],[0,5]], cost = [1,2,3,4,5,6]
16 * Output: [120,1,1,1,1,1]
17 * 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.
18 * 
19 * <strong class="example">Example 2:
20 * <img alt="" src="https://assets.leetcode.com/uploads/2023/11/09/screenshot-2023-11-10-012614.png" style="width: 800px; height: 374px;" />
21 * 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]
22 * Output: [280,140,32,1,1,1,1,1,1]
23 * Explanation: The coins placed on each node are:
24 * - Place 8 * 7 * 5 = 280 coins on node 0.
25 * - Place 7 * 5 * 4 = 140 coins on node 1.
26 * - Place 8 * 2 * 2 = 32 coins on node 2.
27 * - All other nodes are leaves with subtree of size 1, place 1 coin on each of them.
28 * 
29 * <strong class="example">Example 3:
30 * <img alt="" src="https://assets.leetcode.com/uploads/2023/11/09/screenshot-2023-11-10-012513.png" style="width: 300px; height: 277px;" />
31 * Input: edges = [[0,1],[0,2]], cost = [1,2,-2]
32 * Output: [0,1,1]
33 * 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.
34 * 
35 *  
36 * Constraints:
37 * 
38 * 	2 <= n <= 2 * 10^4
39 * 	edges.length == n - 1
40 * 	edges[i].length == 2
41 * 	0 <= ai, bi < n
42 * 	cost.length == n
43 * 	1 <= |cost[i]| <= 10^4
44 * 	The input is generated such that edges represents a valid tree.
45 * 
46 */
47pub struct Solution {}
48
49// problem: https://leetcode.com/problems/find-number-of-coins-to-place-in-tree-nodes/
50// discuss: https://leetcode.com/problems/find-number-of-coins-to-place-in-tree-nodes/discuss/?currentPage=1&orderBy=most_votes&query=
51
52// submission codes start here
53
54impl Solution {
55    pub fn placed_coins(edges: Vec<Vec<i32>>, cost: Vec<i32>) -> Vec<i64> {
56        
57    }
58}
59
60// submission codes end
61
62#[cfg(test)]
63mod tests {
64    use super::*;
65
66    #[test]
67    fn test_2973() {
68    }
69}
70