Tap here to switch tabs
Problem
Submissions

Problem: Difference Between Maximum and Minimum Price Sum

Try to solve the Difference Between Maximum and Minimum Price Sum problem.

Statement

There is an undirected, unrooted tree consisting of n nodes labeled from 00 to n −1- 1. You are given the integer n and a 2extD2 ext{D} integer array edges of length n −1- 1, where edges[i] =[ai,bi]= [a_i, b_i] denotes an undirected edge between node aia_i and node bib_i. You are also given an integer array price of length n, where price[i] denotes the price of the node i.

The price sum of a path is defined as the sum of the prices of all nodes visited along that path.

For any chosen root node, the cost is the difference between the maximum price sum of a path starting at the root and ending at any node, and the minimum price sum of a path starting at the root and ending at any node.

Return the maximum possible cost among all possible choices of the root node.

Constraints:

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

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

  • 0≤ai,bi≤‘n‘−10 \leq a_i, b_i \leq `n` - 1

  • edges represents a valid tree.

  • price.length =‘n‘= `n`

  • 1≤1 \leq price[i] ≤105\leq 10^5

⋮
Tap here to switch tabs
Problem
Submissions

Problem: Difference Between Maximum and Minimum Price Sum

Try to solve the Difference Between Maximum and Minimum Price Sum problem.

Statement

There is an undirected, unrooted tree consisting of n nodes labeled from 00 to n −1- 1. You are given the integer n and a 2extD2 ext{D} integer array edges of length n −1- 1, where edges[i] =[ai,bi]= [a_i, b_i] denotes an undirected edge between node aia_i and node bib_i. You are also given an integer array price of length n, where price[i] denotes the price of the node i.

The price sum of a path is defined as the sum of the prices of all nodes visited along that path.

For any chosen root node, the cost is the difference between the maximum price sum of a path starting at the root and ending at any node, and the minimum price sum of a path starting at the root and ending at any node.

Return the maximum possible cost among all possible choices of the root node.

Constraints:

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

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

  • 0≤ai,bi≤‘n‘−10 \leq a_i, b_i \leq `n` - 1

  • edges represents a valid tree.

  • price.length =‘n‘= `n`

  • 1≤1 \leq price[i] ≤105\leq 10^5