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

from collections import defaultdict
from typing import List

class Solution:
    def maxOutput(self, n: int, edges: List[List[int]], price: List[int]) -> int:
        # Step 1: Build the graph representation of the tree
        g = defaultdict(list)
        for a, b in edges:
            g[a].append(b)
            g[b].append(a)

        # Step 2: Define a DFS function to calculate the state for each node
        def dfs(node1, node2=-1):
            # Initialize the state for the current node
            p = price[node1]
            state = (0, p, 0)

            # Traverse all connected nodes
            for n in g[node1]:
                if n == node2: 
                    continue

                # Get the state of the connected node
                (a1, a2, a3), (b1, b2, b3) = state, dfs(n, node1)
                
                # Update the state based on the recurrence relation
                state = (
                    max(a1, b1, a2 + b3, a3 + b2),
                    max(a2, b2 + p),
                    max(a3, b3 + p)
                )

            return state

        # Step 3: Handle the base case where n <= 2
        if n <= 2:
            return sum(price) - min(price)

        # Step 4: Find the maximum possible cost by rooting the tree at each node
        for node in range(n):
            if len(g[node]) > 1:
                return dfs(node)[0]

# Explanation:
# - The graph is built using a defaultdict to store adjacency lists.
# - The dfs function calculates a state for each node, which consists of three values:
#   1. The maximum difference between any two paths starting at this node.
#   2. The maximum path sum starting at this node and including this node.
#   3. The maximum path sum starting at this node but not including this node.
# - The recurrence relation updates the state by considering paths through connected nodes.
# - The solution iterates over each node to find the maximum possible cost when the tree is rooted at that node.
# - The time complexity is O(N) because each node and edge is visited once.
# - The space complexity is O(N) due to the storage of the graph and recursion stack.
59200