<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:
        # 1 <= price[i] <= 10^^5
        # min value is value of the root itself
        # find max value from the root to any leaf
        
        
        graph = defaultdict(list)
        for u, v in edges:
            graph[u].append(v)
            graph[v].append(u)
            
        
        rtl = [[] for _ in range(n)]
        # first traversal to find the node to leaf path from each of the node (assume 0 is the root)
        def traverse1(node, parent):
            for nei in graph[node]:
                if nei == parent: continue
                traverse1(nei, node)
                
                child = rtl[nei][-1] # the max entry
                rtl[node].append(child + price[node])
                
            if not rtl[node]:
                rtl[node].append(price[node])
            
            rtl[node].sort()
            rtl[node] = rtl[node][-2:]  # keep at most 2 entry, we dont need more
            
        traverse1(0, -1)
        
        ans = 0
        # second traversal to compute the result from the parent, max parent path that not going through the current node
        def traverse2(node, parent):
            if parent != -1:
                if len(rtl[parent]) == 1: # only 1 path
                    rtl[node].append(price[parent] + price[node])
                else:
                    if rtl[node][-1] + price[parent] == rtl[parent][-1]: # this is the longest path, we take the next longest
                        rtl[node].append(rtl[parent][-2] + price[node])
                    else:
                        rtl[node].append(rtl[parent][-1] + price[node])
            
            rtl[node].sort()
            for nei in graph[node]:
                if nei == parent:
                    continue
                
                traverse2(nei, node)
            
        traverse2(0, -1)
        return max(rtl[i][-1] - price[i] for i in range(n))
                
        
        
        
        
74400