Watch 3 video solutions for Choose Edges to Maximize Score in a Tree, a medium level problem involving Dynamic Programming, Tree, Depth-First Search. This walkthrough by Code-Yao has 555 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
You are given a weighted tree consisting of n nodes numbered from 0 to n - 1.
The tree is rooted at node 0 and represented with a 2D array edges of size n where edges[i] = [pari, weighti] indicates that node pari is the parent of node i, and the edge between them has a weight equal to weighti. Since the root does not have a parent, you have edges[0] = [-1, -1].
Choose some edges from the tree such that no two chosen edges are adjacent and the sum of the weights of the chosen edges is maximized.
Return the maximum sum of the chosen edges.
Note:
0.Edge1 and Edge2 in the tree are adjacent if they have a common node.
Edge1 connects nodes a and b and Edge2 connects nodes b and c.
Example 1:
Input: edges = [[-1,-1],[0,5],[0,10],[2,6],[2,4]] Output: 11 Explanation: The above diagram shows the edges that we have to choose colored in red. The total score is 5 + 6 = 11. It can be shown that no better score can be obtained.
Example 2:
Input: edges = [[-1,-1],[0,5],[0,-6],[0,7]] Output: 7 Explanation: We choose the edge with weight 7. Note that we cannot choose more than one edge because all edges are adjacent to each other.
Constraints:
n == edges.length1 <= n <= 105edges[i].length == 2par0 == weight0 == -10 <= pari <= n - 1 for all i >= 1.pari != i-106 <= weighti <= 106 for all i >= 1.edges represents a valid tree.Problem Overview: You are given a rooted tree where each edge has a score. The goal is to choose a subset of edges that maximizes the total score, with the constraint that no two chosen edges share a node. This is essentially a maximum weight matching problem on a tree.
Approach 1: Brute Force Edge Selection (Exponential Time)
Generate all subsets of edges and keep only those where no two edges share a node. For each valid subset, compute the total score and track the maximum. This approach checks every combination, so the time complexity grows exponentially, roughly O(2^n), with O(n) space for recursion or subset storage. It demonstrates the constraint clearly but becomes infeasible even for moderate tree sizes.
Approach 2: Tree Dynamic Programming with DFS (O(n) time, O(n) space)
The optimal strategy uses dynamic programming on a tree combined with depth-first search. Traverse the tree bottom‑up and compute two states for every node u. The first state represents the best score when u is free to connect to one of its children. The second state represents the case where u is already matched with its parent, meaning it cannot select any child edges.
During DFS, aggregate results from children. Start with a base value equal to the sum of the "free" scores from each child (no edge chosen between u and that child). Then evaluate whether selecting the edge (u, v) improves the total: the gain equals the edge weight plus the child's "parent-used" state minus its "free" state. Only one child edge can be selected because choosing it consumes node u. Track the maximum gain and add it to the base if it is positive.
This DP structure guarantees each subtree is processed once, giving O(n) time and O(n) space for adjacency lists and recursion. The algorithm effectively computes the maximum weighted matching for a tree.
Recommended for interviews: Tree DP with DFS is the expected solution. Brute force shows you understand the matching constraint, but the DP formulation demonstrates the ability to model state transitions on trees and reduce the complexity to linear time.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Edge Subsets | O(2^n) | O(n) | Conceptual understanding of constraints; impractical for real inputs |
| Tree DP with DFS | O(n) | O(n) | Optimal approach for trees; computes maximum weighted matching efficiently |