Minimum Increments to Equalize Leaf Paths
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.
Each node i has an associated cost given by cost[i], representing the cost to traverse that node.
The score of a path is defined as the sum of the costs of all nodes along the path.
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.
Return the minimum number of nodes whose cost must be increased to make all root-to-leaf path scores equal.
Example 1
Input
n = 3, edges = [[0,1],[0,2]], cost = [2,1,3]Output
1Increasing the cost of node 1 by 2 makes the two root-to-leaf path scores both equal to 5, so only one node is increased.
Example 2
Input
n = 3, edges = [[0,1],[1,2]], cost = [5,1,4]Output
0There is only one root-to-leaf path, so all path costs are trivially equal and no node must be increased.
Constraints
- 2 <= n <= 10^5
- edges.length == n - 1
- edges[i] == [ui, vi]
- 0 <= ui, vi < n
- cost.length == n
- 1 <= cost[i] <= 10^9
- The input is generated such that edges represents a valid tree.