Skip to main content
Talentd

Choose Edges to Maximize Score in a Tree - Solution & Explanation

MediumPremiumFree on FleetCodeDynamic ProgrammingTreeDepth-First Search11 min readAsked at: Sprinklr
Practice this problem

Problem Statement

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:

  • You are allowed to not choose any edges in the tree, the sum of weights in this case will be 0.
  • Two edges Edge1 and Edge2 in the tree are adjacent if they have a common node.
    • In other words, they are adjacent if 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.length
  • 1 <= n <= 105
  • edges[i].length == 2
  • par0 == weight0 == -1
  • 0 <= pari <= n - 1 for all i >= 1.
  • pari != i
  • -106 <= weighti <= 106 for all i >= 1.
  • edges represents a valid tree.

Approach Overview

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.

Solution

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:

  • If the edge between 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.
  • If the edge between 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.

Code

PythonJavaC++Go

Python

Java

C++

Go

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force Edge SubsetsO(2^n)O(n)Conceptual understanding of constraints; impractical for real inputs
Tree DP with DFSO(n)O(n)Optimal approach for trees; computes maximum weighted matching efficiently

Video Solution

Leetcode 2378. Choose Edges to Maximize Score in a Tree - graph and dynamic programming • Code-Yao • 567 views views

Watch 2 more video solutions →

Frequently Asked Questions

Is Choose Edges to Maximize Score in a Tree easy or hard?
The problem is generally considered Medium difficulty on LeetCode. The challenge comes from recognizing it as a maximum weight matching problem on a tree and modeling the correct DP states during DFS.
Choose Edges to Maximize Score in a Tree Python/Java solution
Most implementations follow the same Tree DP pattern. Build the adjacency list, run DFS, and return two values per node representing the DP states. The logic translates directly across Python, Java, C++, and Go because it only relies on recursion and array-based adjacency lists.
How to solve Choose Edges to Maximize Score in a Tree in O(n)?
Build an adjacency list for the tree and run a DFS from the root. For every node, compute two values: the best score when the node is free and when it is already matched with its parent. Aggregate child results, compute the base sum of child contributions, and optionally add the best gain from selecting one child edge. Each node is processed once, giving linear time complexity.
What is the best approach for Choose Edges to Maximize Score in a Tree?
The best approach is Tree Dynamic Programming combined with Depth-First Search. For each node, compute two DP states: one when the node is free to connect to a child and one when it is already matched with its parent. This allows evaluating whether selecting a specific edge improves the total score while respecting the constraint that no node participates in more than one chosen edge.
Is Choose Edges to Maximize Score in a Tree asked at Google/Amazon/Meta?
Tree DP and maximum matching style problems frequently appear in interviews at companies like Google, Amazon, and Meta. Variations include selecting edges or nodes in trees under constraints, making this problem a good practice example for advanced tree dynamic programming patterns.
What data structure is used in Choose Edges to Maximize Score in a Tree?
The solution uses an adjacency list to represent the tree and recursion (DFS) to traverse it. Dynamic programming arrays or tuples store two states per node, representing whether the node is free or already matched with its parent.
What is the time complexity of Choose Edges to Maximize Score in a Tree?
The optimal Tree DP solution runs in O(n) time because each node and edge in the tree is processed once during DFS. The space complexity is O(n) for the adjacency list and recursion stack used to store DP states for each node.

Ready to solve this problem?

Practice Choose Edges to Maximize Score in a Tree with our built-in code editor and test cases.

Practice on FleetCode
Previous

Binary Tree Cameras

Next

Longest Path With Different Adjacent Characters