Choose Edges to Maximize Score in a Tree - Practice Coding Problems

Choose Edges to Maximize Score in a Tree - Problem

Choose Edges to Maximize Score in a Tree

Imagine you're a network engineer tasked with selecting optimal connections in a tree network to maximize bandwidth utilization. You have a weighted tree with n nodes numbered from 0 to n-1, rooted at node 0.

The tree structure is given as a 2D array edges where edges[i] = [parent_i, weight_i] indicates that parent_i is the parent of node i, and the edge between them has weight weight_i. The root node has edges[0] = [-1, -1] since it has no parent.

Your challenge: Select a subset of edges such that no two selected edges share a common node (are adjacent), and the sum of their weights is maximized.

Goal: Return the maximum possible sum of edge weights you can achieve.

Key constraint: Two edges are considered adjacent if they share any common node. For example, edges connecting (A↔B) and (B↔C) are adjacent because they both connect to node B.

Input & Output

example_1.py — Basic Tree

$ Input: edges = [[-1,-1],[0,5],[0,3],[1,4]]

› Output: 7

💡 Note: Tree structure: 0->1->3, 0->2. We can select edges (0,2) with weight 3 and (1,3) with weight 4. These edges don't share nodes, giving sum = 3 + 4 = 7.

example_2.py — Single Path

$ Input: edges = [[-1,-1],[0,2],[1,3],[2,1]]

› Output: 3

💡 Note: Linear tree: 0->1->2->3. We can only select one edge due to adjacency constraints. Choose edge (1,2) with weight 3 for maximum sum.

example_3.py — Single Node

$ Input: edges = [[-1,-1]]

› Output: 0

💡 Note: Tree with only root node has no edges to select, so maximum sum is 0.

Constraints

1 ≤ n ≤ 10⁵
edges.length == n
edges[i].length == 2
0 ≤ parent_i ≤ n - 1
-10⁶ ≤ weight_i ≤ 10⁶
edges[0] = [-1, -1]
The input represents a valid tree

Visualization

Tap to expand

Understanding the Visualization

Identify the Tree Structure

Parse the parent-child relationships to build the tree representation

Define the Choice at Each Node

For each node, decide whether to include the edge to its parent

Apply the Constraint

If we include a parent edge, we cannot include any child edges

Optimize with DP

Use dynamic programming to efficiently compute the optimal choice for each subtree

Key Takeaway

🎯 Key Insight: Transform the edge selection problem into a node-based DP where each node decides whether to include its parent edge, naturally handling the adjacency constraint through the tree structure.

Asked in

G Google 45 a Amazon 38 f Meta 32 ⊞ Microsoft 28

The optimal solution uses dynamic programming on trees with O(n) time complexity. For each node, we maintain two states: the maximum score when including the edge to its parent versus excluding it. The key insight is that including a parent edge prevents selecting any child edges due to adjacency constraints. This creates a perfect subproblem structure that DP can solve efficiently.

Common Approaches

Approach	Time	Space	Notes
✓ Dynamic Programming on Tree (Optimal)	O(n)	O(n)	Use tree DP with two states per node: include/exclude parent edge
Brute Force (Try All Combinations)	O(2^n × n²)	O(n)	Generate all possible edge combinations and check adjacency constraints

Dynamic Programming on Tree (Optimal) — Algorithm Steps

Build the tree structure from the edges array
Define DP states: dp[node][0] = max sum excluding parent edge, dp[node][1] = max sum including parent edge
Perform DFS traversal starting from leaves
For each node: if including parent edge, sum all children's dp[child][0] values
If excluding parent edge, sum max(dp[child][0], dp[child][1]) for all children
Return dp[0][0] (root has no parent edge)

Visualization

Tap to expand

Step-by-Step Walkthrough

Build Tree

Construct adjacency list representation of the tree

Define DP States

For each node: dp[0] = exclude parent edge, dp[1] = include parent edge

Bottom-up Computation

Compute optimal values from leaves to root using recurrence relation

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct Node {
    int child;
    int weight;
    struct Node* next;
} Node;

Node* children[10000];
int n;

void addChild(int parent, int child, int weight) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->child = child;
    newNode->weight = weight;
    newNode->next = children[parent];
    children[parent] = newNode;
}

void dfs(int node, int* exclude, int* include) {
    *exclude = 0;
    *include = 0;
    
    Node* curr = children[node];
    while (curr) {
        int childExclude, childInclude;
        dfs(curr->child, &childExclude, &childInclude);
        
        *exclude += (childInclude > childExclude) ? childInclude : childExclude;
        *include += childExclude;
        
        curr = curr->next;
    }
}

int maxScore(int** edges, int edgesSize, int* edgesColSize) {
    if (edgesSize <= 1) return 0;
    
    n = edgesSize;
    memset(children, 0, sizeof(children));
    
    // Build adjacency list
    for (int i = 1; i < n; i++) {
        if (edges[i][0] != -1) {
            addChild(edges[i][0], i, edges[i][1]);
        }
    }
    
    int exclude, include;
    dfs(0, &exclude, &include);
    
    // Free memory
    for (int i = 0; i < n; i++) {
        Node* curr = children[i];
        while (curr) {
            Node* temp = curr;
            curr = curr->next;
            free(temp);
        }
    }
    
    return exclude; // Root has no parent edge
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Single DFS traversal visiting each node exactly once

✓ Linear Growth

Space Complexity

O(n)

Recursion stack depth and adjacency list storage

⚡ Linearithmic Space

31.7K Views

Medium Frequency

~25 min Avg. Time

1.3K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Dynamic Programming on Tree (Optimal) — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler