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.
We design a function dfs(i), which represents the maximum sum of the weights of selected edges in the subtree rooted at node i, such that no two selected edges are adjacent. This function returns two values (a, b). The first value a represents the sum of the weights of selected edges when the edge between the current node i and its parent node is selected. The second value b represents the sum of the weights of selected edges when the edge between the current node i and its parent node is not selected.
We can observe the following for the current node i:
i and its parent node is selected, then none of the edges between i and its child nodes can be selected. In this case, the value of a for the current node is the sum of the b values of all its child nodes.i and its parent node is not selected, then we can select at most one edge between i and its child nodes. In this case, the value of b for the current node is the sum of the a values of the selected child nodes and the b values of the unselected child nodes, plus the weight of the edge between i and the selected child node.We call the function dfs(0), and the second value returned is the answer, which is the sum of the weights of selected edges when the edge between the root node and its parent node is not selected.
The time complexity is O(n), and the space complexity is O(n). Here, n is the number of nodes.
| 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 |
Leetcode 2378. Choose Edges to Maximize Score in a Tree - graph and dynamic programming • Code-Yao • 555 views views
Watch 2 more video solutions →Practice Choose Edges to Maximize Score in a Tree with our built-in code editor and test cases.
Practice on FleetCode