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.

Description Hints 4 Solution Video 23:12

2378. Choose Edges to Maximize Score in a Tree

Medium57.1% acceptance1 companyPremium elsewhere, free here

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] = [par_i, weight_i] indicates that node par_i is the parent of node i, and the edge between them has a weight equal to weight_i. 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 Edge₁ and Edge₂ in the tree are adjacent if they have a common node.
- In other words, they are adjacent if Edge₁ connects nodes a and b and Edge₂ 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 <= 10⁵
edges[i].length == 2
par₀ == weight₀ == -1
0 <= par_i <= n - 1 for all i >= 1.
par_i != i
-10⁶ <= weight_i <= 10⁶ for all i >= 1.
edges represents a valid tree.

Asked at 1 company

Sprinklr

Topics

Hints open one at a time

Hint 1

Use dynamic programming to recursively solve the problem for smaller subtrees.

Hint 2

You can ignore the edges with negative weights.

Hint 3

The states of the dp are the following: the root of the subtree you are at, and a boolean variable that will tell you if you have chosen the edge that connects that node and its parent.

Hint 4

What are the transitions of this dp?

23:12

Still stuck?Read the written solution, or watch a walkthrough.

Open solution