Problem. A path is a sequence of nodes where each adjacent pair is connected by an edge, with no node repeated; it doesn't have to pass through the root, and it has at least one node. Return the maximum sum of node values over all paths. Values can be negative.
-10
/ \
9 20 → 42 (15 → 20 → 7)
/ \
15 7
-3 → -3 (a single node; every path must have one)
It's lesson 10.5's diameter with values instead of edge counts. The new twist is negativity: an arm that sums to less than zero should be dropped, not extended, and an all-negative tree still has to return its best single node.
ML context. Picture a tree of decisions where each node carries a score (a log-probability, a reward, a gain minus a cost), and you want the best-scoring chain: the most likely chain of hierarchical labels, the most profitable sequence of follow-up actions, the strongest chain of evidence through a tree of retrieved documents. Negative scores are exactly the "don't go there" signal this problem handles (Change D).