Maximum Subgraph Score in a Tree solution and explanation
The problem
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:
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:
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 of3 - 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 of3 - 1 = 2.
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 <= 105edges.length == n - 1edges[i] = [ai, bi]0 <= ai, bi < ngood.length == n0 <= good[i] <= 1- The input is generated such that
edgesrepresents 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.
The written solution for this problem is still being prepared. Try it yourself in the meantime.
Try solving it yourselfComplexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force DFS from Every Node | O(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 Arrays | O(n) | O(n) | Preferred when recursion depth could overflow or when implementing explicit stacks |
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.