3593. Minimum Increments to Equalize Leaf Paths Medium

1/**
2 * [3593] Minimum Increments to Equalize Leaf Paths
3 *
4 * You are given an integer n and an undirected tree rooted at node 0 with n nodes numbered from 0 to n - 1. This is represented by a 2D array edges of length n - 1, where edges[i] = [ui, vi] indicates an edge from node ui to vi .
5 * Each node i has an associated cost given by cost[i], representing the cost to traverse that node.
6 * The score of a path is defined as the sum of the costs of all nodes along the path.
7 * Your goal is to make the scores of all root-to-leaf paths equal by increasing the cost of any number of nodes by any non-negative amount.
8 * Return the minimum number of nodes whose cost must be increased to make all root-to-leaf path scores equal.
9 *  
10 * <strong class="example">Example 1:
11 * <div class="example-block">
12 * Input: <span class="example-io">n = 3, edges = [[0,1],[0,2]], cost = [2,1,3]</span>
13 * Output: <span class="example-io">1</span>
14 * Explanation:
15 * <img src="https://assets.leetcode.com/uploads/2025/05/28/screenshot-2025-05-28-at-134018.png" style="width: 180px; height: 145px;" />
16 * There are two root-to-leaf paths:
17 * 
18 * 	Path 0 &rarr; 1 has a score of 2 + 1 = 3.
19 * 	Path 0 &rarr; 2 has a score of 2 + 3 = 5.
20 * 
21 * To make all root-to-leaf path scores equal to 5, increase the cost of node 1 by 2.<br />
22 * Only one node is increased, so the output is 1.
23 * </div>
24 * <strong class="example">Example 2:
25 * <div class="example-block">
26 * Input: <span class="example-io">n = 3, edges = [[0,1],[1,2]], cost = [5,1,4]</span>
27 * Output: <span class="example-io">0</span>
28 * Explanation:
29 * <img src="https://assets.leetcode.com/uploads/2025/05/28/screenshot-2025-05-28-at-134249.png" style="width: 230px; height: 75px;" />
30 * There is only one root-to-leaf path:
31 * 
32 * 	
33 * 	Path 0 &rarr; 1 &rarr; 2 has a score of 5 + 1 + 4 = 10.
34 * 	
35 * 
36 * Since only one root-to-leaf path exists, all path costs are trivially equal, and the output is 0.
37 * </div>
38 * <strong class="example">Example 3:
39 * <div class="example-block">
40 * Input: <span class="example-io">n = 5, edges = [[0,4],[0,1],[1,2],[1,3]], cost = [3,4,1,1,7]</span>
41 * Output: <span class="example-io">1</span>
42 * Explanation:
43 * <img src="https://assets.leetcode.com/uploads/2025/05/28/screenshot-2025-05-28-at-135704.png" style="width: 267px; height: 250px;" />
44 * There are three root-to-leaf paths:
45 * 
46 * 	Path 0 &rarr; 4 has a score of 3 + 7 = 10.
47 * 	Path 0 &rarr; 1 &rarr; 2 has a score of 3 + 4 + 1 = 8.
48 * 	Path 0 &rarr; 1 &rarr; 3 has a score of 3 + 4 + 1 = 8.
49 * 
50 * To make all root-to-leaf path scores equal to 10, increase the cost of node 1 by 2. Thus, the output is 1.
51 * </div>
52 *  
53 * Constraints:
54 * 
55 * 	2 <= n <= 10^5
56 * 	edges.length == n - 1
57 * 	edges[i] == [ui, vi]
58 * 	0 <= ui, vi < n
59 * 	cost.length == n
60 * 	1 <= cost[i] <= 10^9
61 * 	The input is generated such that edges represents a valid tree.
62 * 
63 */
64pub struct Solution {}
65
66// problem: https://leetcode.com/problems/minimum-increments-to-equalize-leaf-paths/
67// discuss: https://leetcode.com/problems/minimum-increments-to-equalize-leaf-paths/discuss/?currentPage=1&orderBy=most_votes&query=
68
69// submission codes start here
70
71impl Solution {
72    pub fn min_increase(n: i32, edges: Vec<Vec<i32>>, cost: Vec<i32>) -> i32 {
73        0
74    }
75}
76
77// submission codes end
78
79#[cfg(test)]
80mod tests {
81    use super::*;
82
83    #[test]
84    fn test_3593() {
85    }
86}
87