Choose Edges to Maximize Score in a Tree

Choose Edges to Maximize Score in a Tree

What is this problem about?

Given a tree with $n$ nodes where each edge has a weight, you need to choose a subset of edges such that no two chosen edges share a common vertex. The goal is to maximize the sum of the weights of the chosen edges. This is essentially the Maximum Weight Matching problem, but specifically restricted to a tree structure.

Why is this asked in interviews?

Sprinklr and other companies ask this to test your proficiency in Tree Dynamic Programming. While matching in a general graph is complex, matching in a tree is a classic application of the "include-exclude" DP principle. It evaluates whether you can define recursive states that capture whether a node is "available" to be matched with its parent.

Algorithmic pattern used

The primary pattern is Tree DP (Post-order DFS). For each node $u$, we maintain two values:

1. dp[u][0]: The maximum score if node $u$ is NOT matched with any of its children.
2. dp[u][1]: The maximum score if node $u$ IS matched with exactly one of its children. The result for node $u$ depends on the best results from its children. To calculate dp[u][1], you iterate through each child $v$, matching it with $u$ and taking the best "unmatched" result from all other children.

Example explanation

Tree: 0-1 (wt: 5), 0-2 (wt: 10)

1. At node 1: dp[1][0] = 0, dp[1][1] = -inf (no children to match).
2. At node 2: dp[2][0] = 0, dp[2][1] = -inf.
3. At node 0:
   • Option A (No match): max(dp[1][0], dp[1][1]) + max(dp[2][0], dp[2][1]) = 0.
   • Option B (Match 0-1): wt(0,1) + dp[1][0] + max(dp[2][0], dp[2][1]) = 5 + 0 + 0 = 5.
   • Option C (Match 0-2): wt(0,2) + dp[2][0] + max(dp[1][0], dp[1][1]) = 10 + 0 + 0 = 10. The max score is 10.

Common mistakes candidates make

A common error is trying a greedy approach (always picking the heaviest edge), which fails for cases where picking a medium edge allows for two other medium edges to be picked. Another mistake is not handling the case where a child itself might be better off matched with its own child rather than its parent. Properly defining the DP state to handle this "local vs global" trade-off is the key challenge.

Interview preparation tip

Practice "node-based" DP on trees. Usually, these problems involve a state like dp[node][state], where state represents a binary condition (e.g., node is colored/uncolored, node is matched/unmatched).