Maximum Subgraph Score in a Tree - Video Solutions
Maximum Subgraph Score in a Tree | Weekly Contest 479 | Leetcode 3772 Q3 | Tree dp + Rerouting
Maximum Subgraph Score in a Tree - Video Solution
Watch 2 video solutions for Maximum Subgraph Score in a Tree, a hard level problem involving Array, Dynamic Programming, Tree. This walkthrough by Study Placement has 702 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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:
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.
Complexity 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 |