Skip to main content
Talentd

Maximum Subgraph Score in a Tree - Solution & Explanation

HardArrayDynamic ProgrammingTreeDepth-First Search4 min readAsked at: Microsoft
Practice this problem

Problem Statement

You are given an undirected tree with n nodes, numbered from 0 to n - 1. It is represented by a 2D integer array edges​​​​​​​ of length n - 1, where edges[i] = [ai, bi] indicates that there is an edge between nodes ai and bi in the tree.

You are also given an integer array good of length n, where good[i] is 1 if the ith node is good, and 0 if it is bad.

Define the score of a subgraph as the number of good nodes minus the number of bad nodes in that subgraph.

For each node i, find the maximum possible score among all connected subgraphs that contain node i.

Return an array of n integers where the ith element is the maximum score for node i.

A subgraph is a graph whose vertices and edges are subsets of the original graph.

A connected subgraph is a subgraph in which every pair of its vertices is reachable from one another using only its edges.

 

Example 1:

Tree Example 1

Input: n = 3, edges = [[0,1],[1,2]], good = [1,0,1]

Output: [1,1,1]

Explanation:

  • Green nodes are good and red nodes are bad.
  • For each node, the best connected subgraph containing it is the whole tree, which has 2 good nodes and 1 bad node, resulting in a score of 1.
  • Other connected subgraphs containing a node may have the same score.

Example 2:

Tree Example 2

Input: n = 5, edges = [[1,0],[1,2],[1,3],[3,4]], good = [0,1,0,1,1]

Output: [2,3,2,3,3]

Explanation:

  • Node 0: The best connected subgraph consists of nodes 0, 1, 3, 4, which has 3 good nodes and 1 bad node, resulting in a score of 3 - 1 = 2.
  • Nodes 1, 3, and 4: The best connected subgraph consists of nodes 1, 3, 4, which has 3 good nodes, resulting in a score of 3.
  • Node 2: The best connected subgraph consists of nodes 1, 2, 3, 4, which has 3 good nodes and 1 bad node, resulting in a score of 3 - 1 = 2.

Example 3:

Tree Example 3

Input: n = 2, edges = [[0,1]], good = [0,0]

Output: [-1,-1]

Explanation:

For each node, including the other node only adds another bad node, so the best score for both nodes is -1.

 

Constraints:

  • 2 <= n <= 105
  • edges.length == n - 1
  • edges[i] = [ai, bi]
  • 0 <= ai, bi < n
  • good.length == n
  • 0 <= good[i] <= 1
  • The input is generated such that edges represents a valid tree.

Approach Overview

Problem Overview: You are given a tree where each node contributes a score. The task is to select a connected subgraph (any subset of nodes that remain connected) such that the total score is maximized. Since the structure is a tree, every connected subgraph corresponds to choosing a node and optionally including profitable contributions from its descendants.

Approach 1: Brute Force Enumeration with DFS (O(n^2) time, O(n) space)

Start a DFS from every node and attempt to grow a connected subgraph by exploring all neighbors while tracking visited nodes. For each starting node, compute the total score of the reachable subgraph combinations and keep the maximum. Because each DFS may traverse most of the tree and this process repeats for every node, the total time complexity becomes O(n^2). Space usage is O(n) for recursion and visited tracking. This approach demonstrates the problem structure but quickly becomes too slow for large trees.

Approach 2: Tree Dynamic Programming with Postorder DFS (O(n) time, O(n) space)

The optimal strategy uses dynamic programming on a tree. Perform a postorder depth-first search where each node computes the best contribution it can pass to its parent. For every child, recursively calculate its maximum contribution. If a child's contribution is negative, exclude it because adding it would reduce the subgraph score. Each node aggregates positive child contributions and adds its own value to produce the best connected subgraph rooted at that node. Track a global maximum during traversal.

The key insight: a maximum scoring connected subgraph never includes a subtree with negative contribution. Using max(0, childContribution) ensures only beneficial branches are included. Each edge and node is processed once, giving O(n) time complexity and O(n) space from recursion and adjacency storage. Node values typically come from an array, and the tree is represented with an adjacency list.

Recommended for interviews: Interviewers expect the tree DP solution. Brute force shows you understand that the answer is a connected subgraph, but the optimized DFS with contribution pruning demonstrates strong tree reasoning and dynamic programming skills. The O(n) approach is the standard production‑quality solution.

Solutions for this problem are being prepared.

Try solving it yourself

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force DFS from Every NodeO(n^2)O(n)Useful for understanding connected subgraph exploration or verifying small test cases
Tree Dynamic Programming (Postorder DFS)O(n)O(n)Best general solution for trees; processes each node once and aggregates positive contributions
Iterative DFS with DP ArraysO(n)O(n)Preferred when recursion depth could overflow or when implementing explicit stacks

Video Solution

Maximum Subgraph Score in a Tree | Weekly Contest 479 | Leetcode 3772 Q3 | Tree dp + Rerouting • Study Placement • 702 views views

Watch 1 more video solutions →

Frequently Asked Questions

Is Maximum Subgraph Score in a Tree easy or hard?
Maximum Subgraph Score in a Tree is categorized as a Hard problem because it combines tree traversal with dynamic programming reasoning. Recognizing that negative subtree contributions should be excluded is the key insight needed for the optimal O(n) solution.
Maximum Subgraph Score in a Tree Python/Java solution
The standard implementation performs a DFS that returns the maximum contribution from each subtree. The same logic works in Python, Java, C++, and Go using recursion or an explicit stack. Each language builds an adjacency list and aggregates positive child scores.
How to solve Maximum Subgraph Score in a Tree in O(n)?
Build an adjacency list and run a postorder DFS from any root. For every node, recursively compute contributions from its children and add only positive ones to the current node's score. Track a global maximum during traversal to record the best connected subgraph found in the tree.
What is the best approach for Maximum Subgraph Score in a Tree?
The most efficient approach is tree dynamic programming using a postorder DFS traversal. Each node calculates the best contribution from its children and ignores negative contributions using max(0, childValue). This guarantees the maximum connected subgraph score while processing each node once, giving O(n) time complexity.
Is Maximum Subgraph Score in a Tree asked at Google/Amazon/Meta?
Tree dynamic programming problems similar to Maximum Subgraph Score in a Tree frequently appear in interviews at companies like Google, Amazon, and Meta. They test understanding of DFS traversal, subtree aggregation, and pruning negative contributions in tree structures.
What data structure is used in Maximum Subgraph Score in a Tree?
The solution uses an adjacency list to represent the tree and depth‑first search for traversal. Dynamic programming values are stored during recursion to compute each node's best contribution from its subtree.
What is the time complexity of Maximum Subgraph Score in a Tree?
The optimal solution runs in O(n) time where n is the number of nodes in the tree. A single DFS traversal processes each node and edge once while computing the best subgraph contribution. Space complexity is O(n) due to recursion and adjacency list storage.

Ready to solve this problem?

Practice Maximum Subgraph Score in a Tree with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays