<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>

class Solution:
    def maxOutput(self, n: int, edges: List[List[int]], price: List[int]) -> int:
        # it is the same problem as the finding the maximum path sum of a tree
        
        # step 1, build the graph
        self.G = collections.defaultdict(list)
        for s, e in edges:
            self.G[s].append(e)
            self.G[e].append(s)

        self.visited = set()
        self.price = price
        self.ans = 0

        # step 2, start from a random node and DFS traverse the graph
        #   the maximum path sum will be updated during the traversal, and we can
        #   return the result after the traversal is done.
        self.dfs(0)
        
        # Since we are using the min heap to track the maximum, we need to return - self.ans
        return -self.ans

    
    def dfs(self, idx):
        self.visited.add(idx)

        ps_f_list, ps_p_list = [], []

        for nidx in self.G[idx]:
            # for each visiting child we need to get:
            # (1) the maximum path sum with the end node
            # (2) the maximum path sum without the end node
            # We are calculating the difference between maximum path sum and minimum path sum,
            # the price is always postive, therefore, the minimum path sum is always the root value. When we find a path sum, the maximum difference is the path sum - root value.
            # The root value can be at any end of this path.
            # Thus, we need to track two path sum: one is with the end node value, one is not.
            if nidx not in self.visited:
                ps_full, ps_partial = self.dfs(nidx)
                heapq.heappush(ps_f_list, (ps_full, nidx))
                heapq.heappush(ps_p_list, (ps_partial, nidx))

        max_val = 0
        if len(ps_f_list) == 1:
            ps_f_max, _ = heapq.heappop(ps_f_list)
            ps_p_max, _ = heapq.heappop(ps_p_list)
            max_val = min(ps_f_max, ps_p_max - self.price[idx])
            fp_max, pp_max = ps_f_max - self.price[idx], ps_p_max - self.price[idx]
        elif len(ps_f_list) > 1:
            ps_f_max, fm_idx = heapq.heappop(ps_f_list)
            ps_p_max, pm_idx = heapq.heappop(ps_p_list)
            if fm_idx != pm_idx:
                max_val = ps_f_max + ps_p_max - self.price[idx]
                fp_max, pp_max = ps_f_max - self.price[idx], ps_p_max - self.price[idx]
            else:
                # get the second bigest price
                ps_f_max_2, _ = heapq.heappop(ps_f_list)
                ps_p_max_2, _ = heapq.heappop(ps_p_list)
                max_val = min(ps_f_max + ps_p_max_2, ps_f_max_2 + ps_p_max) - self.price[idx]
                fp_max, pp_max = ps_f_max - self.price[idx], ps_p_max - self.price[idx]
        else:
            fp_max, pp_max = -self.price[idx], 0

        if max_val < self.ans:
            self.ans = max_val

        return fp_max, pp_max
68700