We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Choose Edges to Maximize Score in a Tree

Number: 2517

Difficulty: Medium

Paid? Yes

Companies: Sprinklr

Problem Description

Given a weighted tree (represented with an array where each entry indicates the parent and weight of the edge connecting a node to its parent), choose a subset of edges such that no two selected edges are adjacent (i.e. share a common node) and the total sum of weights is maximized. Note that you may choose no edge at all if that yields a better result.

Key Insights

  • The tree is rooted at node 0 and every edge can be thought of as connecting a parent and a child.
  • Two edges are adjacent if they share a node; therefore, if you choose an edge connecting node u to v, neither any other edge incident to u nor any edge incident to v can be chosen.
  • A dynamic programming solution on trees (DFS) is natural. Define two states for each node:
    • A "free" state where the edge from its parent is NOT used, so the node is free to choose one outgoing edge (to one of its children).
    • A "blocked" state where the parent's edge to this node is chosen, so the node cannot use any of its outgoing edges.
  • The recurrence for a node in the free state is the maximum of either not choosing any outgoing edge (taking the sum over children in a free state) or choosing exactly one child edge (which adds the weight of that edge and forces that child into a blocked state, while others remain free).
  • These state transitions allow combining results from subtrees while enforcing the “no adjacent edges” rule.

Space and Time Complexity

Time Complexity: O(n), where n is the number of nodes. Each node is processed once and the children are scanned in O(deg(node)) time. Space Complexity: O(n) for storing the tree structure and the recursion stack.

Solution

We use DFS on the tree and compute two DP values for each node:

  1. dp[node][free]: Maximum sum obtainable from the subtree rooted at node when the edge connecting it to its parent is not selected. Here, the node is free to optionally pick one of its outgoing edges.
  2. dp[node][blocked]: Maximum result when the node is blocked because the parent's edge was chosen. In this case, the node cannot pick any outgoing edge.

For a node in the free state, we:

  • Assume initially that no outgoing edge is selected; summing over all children in the free state.
  • Then, for each child, consider “switching” from free to taking that edge – which contributes weight(child) + dp[child][blocked] instead of dp[child][free]. Only one such edge can be chosen because choosing one edge makes the parent node incident to a chosen edge and invalidates any further picks from that node.

Thus, letting children = all direct children of the node and sum_free = Σ dp[child][free] for each child, we have:   dp[node][free] = sum_free + max(0, max over each child { dp[child][blocked] + weight(child) - dp[child][free] }).

If the node is blocked, then:   dp[node][blocked] = sum_free since no outgoing edge may be chosen.

The final answer is dp[root][free] since the root (node 0) is free (its non-existent parent did not contribute an edge).

Code Solutions

# Python implementation using DFS recursion
from collections import defaultdict
import sys
sys.setrecursionlimit(10**6)

def maxScore(edges):
    n = len(edges)
    # Build tree from parent representation
    tree = defaultdict(list)
    weights = {}
    for i in range(1, n):
        parent, weight = edges[i]
        tree[parent].append(i)
        weights[i] = weight

    # dp[node] = (free, blocked)
    def dfs(node):
        # Initialize sum over children when not choosing an edge from this node
        sum_free = 0
        best_improve = 0  # maximum improvement when choosing one child edge
        for child in tree[node]:
            child_free, child_blocked = dfs(child)
            sum_free += child_free
            # Improvement if we choose edge node->child: add weight + child's blocked dp instead of child's free dp
            improvement = child_blocked + weights[child] - child_free
            if improvement > best_improve:
                best_improve = improvement
        # If node is free to choose an edge from itself, possibly add best improvement if it's positive.
        free = sum_free + best_improve
        # If node is blocked, then we cannot choose any edge from node, so dp is just sum_free.
        blocked = sum_free
        return free, blocked

    dp_free, _ = dfs(0)
    return dp_free

# Example usage:
edges1 = [[-1,-1],[0,5],[0,10],[2,6],[2,4]]
print(maxScore(edges1))  # Expected output: 11

edges2 = [[-1,-1],[0,5],[0,-6],[0,7]]
print(maxScore(edges2))  # Expected output: 7
← Back to All Questions