Tap here to switch tabs
Problem
Submissions

Problem: Minimum Increments to Equalize Leaf Paths

Try to solve the Minimum Increments to Equalize Leaf Paths problem.

Statement

You are given an integer n representing the number of nodes in an undirected tree rooted at node 00, with nodes numbered from 00 to n−1n - 1. You are also given a two dimensional integer array edges of length n−1n - 1, where edges[i] =[ui,vi]= [u_i, v_i] denotes an edge connecting nodes uiu_i and viv_i, and an integer array cost of length n, where cost[i] is the cost associated with node i.

The score of a path from the root node 00 to a leaf node is the sum of the costs of all nodes along that path.

You can increase the cost of any node by any positive integer amount.

Return the minimum number of nodes whose costs must be increased such that every root to leaf path has the exact same score.

Constraints:

  • 2≤2 \leq n ≤105\leq 10^5

  • edges.length =n−1= n - 1

  • edges[i] =[ui,vi]= [u_i, v_i]

  • 0≤ui,vi<0 \leq u_i, v_i < n

  • cost.length =n= n

  • 1≤1 \leq cost[i] ≤109\leq 10^9

  • The input is generated such that edges represents a valid tree.

⋮
Tap here to switch tabs
Problem
Submissions

Problem: Minimum Increments to Equalize Leaf Paths

Try to solve the Minimum Increments to Equalize Leaf Paths problem.

Statement

You are given an integer n representing the number of nodes in an undirected tree rooted at node 00, with nodes numbered from 00 to n−1n - 1. You are also given a two dimensional integer array edges of length n−1n - 1, where edges[i] =[ui,vi]= [u_i, v_i] denotes an edge connecting nodes uiu_i and viv_i, and an integer array cost of length n, where cost[i] is the cost associated with node i.

The score of a path from the root node 00 to a leaf node is the sum of the costs of all nodes along that path.

You can increase the cost of any node by any positive integer amount.

Return the minimum number of nodes whose costs must be increased such that every root to leaf path has the exact same score.

Constraints:

  • 2≤2 \leq n ≤105\leq 10^5

  • edges.length =n−1= n - 1

  • edges[i] =[ui,vi]= [u_i, v_i]

  • 0≤ui,vi<0 \leq u_i, v_i < n

  • cost.length =n= n

  • 1≤1 \leq cost[i] ≤109\leq 10^9

  • The input is generated such that edges represents a valid tree.