Difference Between Maximum and Minimum Price Sum
<p>There exists an undirected and initially unrooted tree with <code>n</code> nodes indexed from <code>0</code> to <code>n - 1</code>. You are given the integer <code>n</code> and a 2D integer array <code>edges</code> of length <code>n - 1</code>, where <code>edges[i] = [a<sub>i</sub>, b<sub>i</sub>]</code> indicates that there is an edge between nodes <code>a<sub>i</sub></code> and <code>b<sub>i</sub></code> in the tree.</p>

<p>Each node has an associated price. You are given an integer array <code>price</code>, where <code>price[i]</code> is the price of the <code>i<sup>th</sup></code> node.</p>

<p>The <strong>price sum</strong> of a given path is the sum of the prices of all nodes lying on that path.</p>

<p>The tree can be rooted at any node <code>root</code> of your choice. The incurred <strong>cost</strong> after choosing <code>root</code> is the difference between the maximum and minimum <strong>price sum</strong> amongst all paths starting at <code>root</code>.</p>

<p>Return <em>the <strong>maximum</strong> possible <strong>cost</strong></em> <em>amongst all possible root choices</em>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2022/12/01/example14.png" style="width: 556px; height: 231px;" />
<pre>
<strong>Input:</strong> n = 6, edges = [[0,1],[1,2],[1,3],[3,4],[3,5]], price = [9,8,7,6,10,5]
<strong>Output:</strong> 24
<strong>Explanation:</strong> The diagram above denotes the tree after rooting it at node 2. The first part (colored in red) shows the path with the maximum price sum. The second part (colored in blue) shows the path with the minimum price sum.
- The first path contains nodes [2,1,3,4]: the prices are [7,8,6,10], and the sum of the prices is 31.
- The second path contains the node [2] with the price [7].
The difference between the maximum and minimum price sum is 24. It can be proved that 24 is the maximum cost.
</pre>

<p><strong class="example">Example 2:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2022/11/24/p1_example2.png" style="width: 352px; height: 184px;" />
<pre>
<strong>Input:</strong> n = 3, edges = [[0,1],[1,2]], price = [1,1,1]
<strong>Output:</strong> 2
<strong>Explanation:</strong> The diagram above denotes the tree after rooting it at node 0. The first part (colored in red) shows the path with the maximum price sum. The second part (colored in blue) shows the path with the minimum price sum.
- The first path contains nodes [0,1,2]: the prices are [1,1,1], and the sum of the prices is 3.
- The second path contains node [0] with a price [1].
The difference between the maximum and minimum price sum is 2. It can be proved that 2 is the maximum cost.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= n &lt;= 10<sup>5</sup></code></li>
	<li><code>edges.length == n - 1</code></li>
	<li><code>0 &lt;= a<sub>i</sub>, b<sub>i</sub> &lt;= n - 1</code></li>
	<li><code>edges</code> represents a valid tree.</li>
	<li><code>price.length == n</code></li>
	<li><code>1 &lt;= price[i] &lt;= 10<sup>5</sup></code></li>
</ul>

['binary-tree-maximum-path-sum']
[]
[{"value": "cpp", "text": "C++", "defaultCode": "class Solution {\npublic:\n    long long maxOutput(int n, vector<vector<int>>& edges, vector<int>& price) {\n        \n    }\n};"}, {"value": "java", "text": "Java", "defaultCode": "class Solution {\n    public long maxOutput(int n, int[][] edges, int[] price) {\n        \n    }\n}"}, {"value": "python", "text": "Python", "defaultCode": "class Solution(object):\n    def maxOutput(self, n, edges, price):\n        \"\"\"\n        :type n: int\n        :type edges: List[List[int]]\n        :type price: List[int]\n        :rtype: int\n        \"\"\"\n        "}, {"value": "python3", "text": "Python3", "defaultCode": "class Solution:\n    def maxOutput(self, n: int, edges: List[List[int]], price: List[int]) -> int:\n        "}, {"value": "c", "text": "C", "defaultCode": "long long maxOutput(int n, int** edges, int edgesSize, int* edgesColSize, int* price, int priceSize) {\n    \n}"}, {"value": "csharp", "text": "C#", "defaultCode": "public class Solution {\n    public long MaxOutput(int n, int[][] edges, int[] price) {\n        \n    }\n}"}, {"value": "javascript", "text": "JavaScript", "defaultCode": "/**\n * @param {number} n\n * @param {number[][]} edges\n * @param {number[]} price\n * @return {number}\n */\nvar maxOutput = function(n, edges, price) {\n    \n};"}, {"value": "typescript", "text": "TypeScript", "defaultCode": "function maxOutput(n: number, edges: number[][], price: number[]): number {\n    \n};"}, {"value": "php", "text": "PHP", "defaultCode": "class Solution {\n\n    /**\n     * @param Integer $n\n     * @param Integer[][] $edges\n     * @param Integer[] $price\n     * @return Integer\n     */\n    function maxOutput($n, $edges, $price) {\n        \n    }\n}"}, {"value": "swift", "text": "Swift", "defaultCode": "class Solution {\n    func maxOutput(_ n: Int, _ edges: [[Int]], _ price: [Int]) -> Int {\n        \n    }\n}"}, {"value": "kotlin", "text": "Kotlin", "defaultCode": "class Solution {\n    fun maxOutput(n: Int, edges: Array<IntArray>, price: IntArray): Long {\n        \n    }\n}"}, {"value": "dart", "text": "Dart", "defaultCode": "class Solution {\n  int maxOutput(int n, List<List<int>> edges, List<int> price) {\n    \n  }\n}"}, {"value": "golang", "text": "Go", "defaultCode": "func maxOutput(n int, edges [][]int, price []int) int64 {\n    \n}"}, {"value": "ruby", "text": "Ruby", "defaultCode": "# @param {Integer} n\n# @param {Integer[][]} edges\n# @param {Integer[]} price\n# @return {Integer}\ndef max_output(n, edges, price)\n    \nend"}, {"value": "scala", "text": "Scala", "defaultCode": "object Solution {\n    def maxOutput(n: Int, edges: Array[Array[Int]], price: Array[Int]): Long = {\n        \n    }\n}"}, {"value": "rust", "text": "Rust", "defaultCode": "impl Solution {\n    pub fn max_output(n: i32, edges: Vec<Vec<i32>>, price: Vec<i32>) -> i64 {\n        \n    }\n}"}, {"value": "racket", "text": "Racket", "defaultCode": "(define/contract (max-output n edges price)\n  (-> exact-integer? (listof (listof exact-integer?)) (listof exact-integer?) exact-integer?)\n  )"}, {"value": "erlang", "text": "Erlang", "defaultCode": "-spec max_output(N :: integer(), Edges :: [[integer()]], Price :: [integer()]) -> integer().\nmax_output(N, Edges, Price) ->\n  ."}, {"value": "elixir", "text": "Elixir", "defaultCode": "defmodule Solution do\n  @spec max_output(n :: integer, edges :: [[integer]], price :: [integer]) :: integer\n  def max_output(n, edges, price) do\n    \n  end\nend"}]
{
  "name": "maxOutput",
  "params": [
    {
      "name": "n",
      "type": "integer"
    },
    {
      "type": "integer[][]",
      "name": "edges"
    },
    {
      "type": "integer[]",
      "name": "price"
    }
  ],
  "return": {
    "type": "long"
  }
}
{"cpp": ["C++", "<p>Compiled with <code> clang 19 </code> using the latest C++ 23 standard, and <code>libstdc++</code> provided by GCC 14.</p>\r\n\r\n<p>Your code is compiled with level two optimization (<code>-O2</code>). <a href=\"https://github.com/google/sanitizers/wiki/AddressSanitizer\" target=\"_blank\">AddressSanitizer</a> is also enabled to help detect out-of-bounds and use-after-free bugs.</p>\r\n\r\n<p>Most standard library headers are already included automatically for your convenience.</p>"], "java": ["Java", "<p><code>OpenJDK 21</code>. Using compile arguments: <code>--enable-preview --release 21</code></p>\r\n\r\n<p>Most standard library headers are already included automatically for your convenience.</p>\r\n<p>Includes <code>Pair</code> class from https://docs.oracle.com/javase/8/javafx/api/javafx/util/Pair.html.</p>"], "python": ["Python", "<p><code>Python 2.7.18</code>.</p>\r\n\r\n<p>Most libraries are already imported automatically for your convenience, such as <a href=\"https://docs.python.org/2/library/array.html\" target=\"_blank\">array</a>, <a href=\"https://docs.python.org/2/library/bisect.html\" target=\"_blank\">bisect</a>, <a href=\"https://docs.python.org/2/library/collections.html\" target=\"_blank\">collections</a>. If you need more libraries, you can import it yourself.</p>\r\n\r\n<p>For Map/TreeMap data structure, you may use <a href=\"http://www.grantjenks.com/docs/sortedcontainers/\" target=\"_blank\">sortedcontainers</a> library.</p>\r\n\r\n<p>Note that Python 2.7 <a href=\"https://www.python.org/dev/peps/pep-0373/\" target=\"_blank\">is not maintained anymore</a>. For the latest Python, please choose Python3 instead.</p>"], "c": ["C", "<p>Compiled with <code>gcc 14</code> using the gnu11 standard.</p>\r\n\r\n<p>Your code is compiled with level one optimization (<code>-O2</code>). <a href=\"https://github.com/google/sanitizers/wiki/AddressSanitizer\" target=\"_blank\">AddressSanitizer</a> is also enabled to help detect out-of-bounds and use-after-free bugs.</p>\r\n\r\n<p>Most standard library headers are already included automatically for your convenience.</p>\r\n\r\n<p>For hash table operations, you may use <a href=\"https://troydhanson.github.io/uthash/\" target=\"_blank\">uthash</a>. \"uthash.h\" is included by default. Below are some examples:</p>\r\n\r\n<p><b>1. Adding an item to a hash.</b>\r\n<pre>\r\nstruct hash_entry {\r\n    int id;            /* we'll use this field as the key */\r\n    char name[10];\r\n    UT_hash_handle hh; /* makes this structure hashable */\r\n};\r\n\r\nstruct hash_entry *users = NULL;\r\n\r\nvoid add_user(struct hash_entry *s) {\r\n    HASH_ADD_INT(users, id, s);\r\n}\r\n</pre>\r\n</p>\r\n\r\n<p><b>2. Looking up an item in a hash:</b>\r\n<pre>\r\nstruct hash_entry *find_user(int user_id) {\r\n    struct hash_entry *s;\r\n    HASH_FIND_INT(users, &user_id, s);\r\n    return s;\r\n}\r\n</pre>\r\n</p>\r\n\r\n<p><b>3. Deleting an item in a hash:</b>\r\n<pre>\r\nvoid delete_user(struct hash_entry *user) {\r\n    HASH_DEL(users, user);  \r\n}\r\n</pre>\r\n</p>"], "csharp": ["C#", "<p><a href=\"https://learn.microsoft.com/en-us/dotnet/csharp/whats-new/csharp-13\" target=\"_blank\">C# 13</a> with .NET 9 runtime</p>"], "javascript": ["JavaScript", "<p><code>Node.js 22.14.0</code>.</p>\r\n\r\n<p>Your code is run with <code>--harmony</code> flag, enabling <a href=\"http://node.green/\" target=\"_blank\">new ES6 features</a>.</p>\r\n\r\n<p><a href=\"https://lodash.com\" target=\"_blank\">lodash.js</a> library is included by default.</p>\r\n\r\n<p>For Priority Queue / Queue data structures, you may use 6.3.2 version of <a href=\"https://github.com/datastructures-js/priority-queue/tree/v6.3.2\" target=\"_blank\">datastructures-js/priority-queue</a> and 4.2.3 version of <a href=\"https://github.com/datastructures-js/queue/tree/v4.2.3\" target=\"_blank\">datastructures-js/queue</a> and 1.0.4 version of <a href=\"https://github.com/datastructures-js/deque/tree/v1.0.4\" target=\"_blank\">datastructures-js/deque</a>.</p>"], "ruby": ["Ruby", "<p><code>Ruby 3.2</code></p>\r\n\r\n<p>Some common data structure implementations are provided in the Algorithms module: https://www.rubydoc.info/github/kanwei/algorithms/Algorithms</p>"], "swift": ["Swift", "<p><code>Swift 6.0</code>.</p>\r\n\r\n<p>You may use the following packages:<br/>\r\n<a href=\"https://github.com/apple/swift-algorithms/tree/1.2.0\" target=\"_blank\">swift-algorithms 1.2.0</a><br/>\r\n<a href=\"https://github.com/apple/swift-collections/tree/1.1.4\" target=\"_blank\">swift-collections 1.1.4</a><br/>\r\n<a href=\"https://github.com/apple/swift-numerics/tree/1.0.2\" target=\"_blank\">swift-numerics 1.0.2</a></p>"], "golang": ["Go", "<p><code>Go 1.23</code></p>\r\n<p>Support <a href=\"https://pkg.go.dev/github.com/emirpasic/gods@v1.18.1\" target=\"_blank\">https://pkg.go.dev/github.com/emirpasic/gods@v1.18.1</a> and <a href=\"https://pkg.go.dev/github.com/emirpasic/gods/v2@v2.0.0-alpha\" target=\"_blank\">https://pkg.go.dev/github.com/emirpasic/gods/v2@v2.0.0-alpha</a> library.</p>"], "python3": ["Python3", "<p><code>Python 3.11</code>.</p>\r\n\r\n<p>Most libraries are already imported automatically for your convenience, such as <a href=\"https://docs.python.org/3/library/array.html\" target=\"_blank\">array</a>, <a href=\"https://docs.python.org/3/library/bisect.html\" target=\"_blank\">bisect</a>, <a href=\"https://docs.python.org/3/library/collections.html\" target=\"_blank\">collections</a>. If you need more libraries, you can import it yourself.</p>\r\n\r\n<p>For Map/TreeMap data structure, you may use <a href=\"http://www.grantjenks.com/docs/sortedcontainers/\" target=\"_blank\">sortedcontainers</a> library.</p>"], "scala": ["Scala", "<p><code>Scala 3.3.1</code>.</p>"], "kotlin": ["Kotlin", "<p><code>Kotlin 2.1.10</code>.</p>"], "rust": ["Rust", "<p><code>Rust 1.85.0</code>. Your code will be compiled with <code>opt-level</code> 2.</p>\r\n\r\n<p>Supports <a href=\"https://crates.io/crates/rand\" target=\"_blank\">rand v0.8</a> and <a href=\"https://crates.io/crates/regex\" target=\"_blank\">regex\u00a0v1</a> and <a href=\"https://crates.io/crates/itertools\" target=\"_blank\">itertools\u00a0v0.14</a> from crates.io</p>"], "php": ["PHP", "<p><code>PHP 8.2</code>.</p>\r\n<p>With bcmath module</p>"], "typescript": ["Typescript", "<p><code>TypeScript 5.7.3, Node.js 22.14.0</code>.</p>\r\n\r\n<p>Compile Options: <code>--alwaysStrict --strictBindCallApply --strictFunctionTypes --target ES2024</code></p>\r\n\r\n<p><a href=\"https://lodash.com\" target=\"_blank\">lodash.js</a> library is included by default.</p>\r\n\r\n<p>For Priority Queue / Queue data structures, you may use 6.3.2 version of <a href=\"https://github.com/datastructures-js/priority-queue/tree/v6.3.2\" target=\"_blank\">datastructures-js/priority-queue</a> and 4.2.3 version of <a href=\"https://github.com/datastructures-js/queue/tree/v4.2.3\" target=\"_blank\">datastructures-js/queue</a> and 1.0.4 version of <a href=\"https://github.com/datastructures-js/deque/tree/v1.0.4\" target=\"_blank\">datastructures-js/deque</a>.</p>"], "racket": ["Racket", "<p><a href=\"https://docs.racket-lang.org/guide/performance.html#%28tech._c%29\" target=\"_blank\">Racket CS</a> v8.15</p>\r\n\r\n<p>Using <code>#lang racket</code></p>\r\n\r\n<p>Required <code>data/gvector data/queue data/order data/heap</code> automatically for your convenience</p>"], "erlang": ["Erlang", "Erlang/OTP 26"], "elixir": ["Elixir", "Elixir 1.17 with Erlang/OTP 26"], "dart": ["Dart", "<p>Dart 3.2. You may use package <a href=\"https://pub.dev/packages/collection/versions/1.18.0\" target=\"_blank\">collection</a></p>\r\n\r\n<p>Your code will be run directly without compiling</p>"]}
['Array', 'Dynamic Programming', 'Tree', 'Depth-First Search']