LeetCode 3772 - Maximum Subgraph Score in a Tree

LeetCode Problem 3772

Difficulty: 🔴 Hard
Topics: Array, Dynamic Programming, Tree, Depth-First Search

Solution

Problem Understanding

The problem asks us to compute, for each node in a tree, the maximum score of a connected subgraph that includes that node. The tree is represented as an undirected graph with n nodes and n - 1 edges. Each node has a value indicating whether it is good (1) or bad (0). The score of a subgraph is calculated as the number of good nodes minus the number of bad nodes.

In other words, for each node, we need to find a connected portion of the tree that includes the node and maximizes the difference between good and bad nodes. The output is an array of integers where each entry corresponds to the maximum score achievable for that node.

Key points to notice:

1. The input is guaranteed to be a tree, so it is connected and acyclic. This means DFS-based algorithms are suitable.
2. The tree can have up to 10^5 nodes, which prohibits any brute-force approach that tries all possible connected subgraphs. We need a linear-time or near-linear-time solution.
3. Edge cases include all nodes being bad, all nodes being good, or unbalanced trees where some nodes are leaves with bad nodes only.

Approaches

Brute Force

A naive approach would attempt to generate all connected subgraphs for each node and compute their scores. This could involve recursive exploration of all possible subgraphs starting from each node. While this approach is correct, it has exponential time complexity O(2^n) and is infeasible for n up to 10^5.

Optimal Approach

The key insight is to use a tree dynamic programming (DP) technique, specifically a variant of the "maximum subarray sum on a tree" problem. We can transform the node values into scores of +1 for good nodes and -1 for bad nodes. Then, we compute two DP passes:

1. Post-order DFS: Compute the maximum score for subtrees rooted at each node. If including a child reduces the score (negative contribution), we ignore it. This gives the best subgraph scores assuming the node is the root of its subtree.
2. Pre-order DFS: Propagate the best scores from parent to children, adjusting for contributions from siblings. This ensures that each node considers subgraphs that may extend beyond its own subtree.

This approach ensures linear-time computation, O(n), as each edge is visited a constant number of times.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(2^n)	O(n)	Generate all connected subgraphs from each node
Optimal	O(n)	O(n)	Tree DP with post-order and pre-order DFS to compute maximum scores

Algorithm Walkthrough

1. Convert the good array into scores, where good[i] = 1 becomes +1 and good[i] = 0 becomes -1. This simplifies score calculations.
2. Build the adjacency list of the tree from the edges array for efficient DFS traversal.
3. Post-order DFS: For each node, recursively compute the maximum subgraph score for each child. Only include children with positive scores to avoid reducing the parent’s score. Store these values as dp[node].
4. Pre-order DFS: For each node, propagate contributions from its parent. For each child, compute the maximum score it can achieve considering the parent’s contribution and other siblings. Update dp[child] accordingly.
5. After both DFS passes, dp[node] will contain the maximum score for each node. Return the array.

Why it works: The first DFS ensures each node knows the best score from its subtree. The second DFS allows each node to consider extending the subgraph beyond its subtree using the parent and sibling contributions. Because trees are acyclic, every subgraph is uniquely determined by this propagation.

Python Solution

from typing import List
from collections import defaultdict

class Solution:
    def maxSubgraphScore(self, n: int, edges: List[List[int]], good: List[int]) -> List[int]:
        score = [1 if x == 1 else -1 for x in good]
        tree = defaultdict(list)
        for u, v in edges:
            tree[u].append(v)
            tree[v].append(u)

        dp = [0] * n

        def post_order(node: int, parent: int) -> int:
            total = score[node]
            for child in tree[node]:
                if child == parent:
                    continue
                child_score = post_order(child, node)
                if child_score > 0:
                    total += child_score
            dp[node] = total
            return total

        def pre_order(node: int, parent: int):
            for child in tree[node]:
                if child == parent:
                    continue
                # Remove child's contribution if positive, then add parent's contribution if positive
                child_contrib = max(0, dp[child])
                dp[child] = dp[child] + max(0, dp[node] - child_contrib)
                pre_order(child, node)

        post_order(0, -1)
        pre_order(0, -1)
        return dp

Explanation: The post_order DFS calculates the best subtree score for each node. The pre_order DFS adjusts each child’s score to include potential contributions from the parent. The max(0, …) ensures that only positive contributions are considered. The final dp array contains the maximum score for each node.

Go Solution

package main

func maxSubgraphScore(n int, edges [][]int, good []int) []int {
    score := make([]int, n)
    for i := 0; i < n; i++ {
        if good[i] == 1 {
            score[i] = 1
        } else {
            score[i] = -1
        }
    }

    tree := make([][]int, n)
    for _, e := range edges {
        u, v := e[0], e[1]
        tree[u] = append(tree[u], v)
        tree[v] = append(tree[v], u)
    }

    dp := make([]int, n)

    var postOrder func(node, parent int) int
    postOrder = func(node, parent int) int {
        total := score[node]
        for _, child := range tree[node] {
            if child == parent {
                continue
            }
            childScore := postOrder(child, node)
            if childScore > 0 {
                total += childScore
            }
        }
        dp[node] = total
        return total
    }

    var preOrder func(node, parent int)
    preOrder = func(node, parent int) {
        for _, child := range tree[node] {
            if child == parent {
                continue
            }
            childContrib := dp[child]
            if childContrib < 0 {
                childContrib = 0
            }
            dp[child] += max(0, dp[node]-childContrib)
            preOrder(child, node)
        }
    }

    postOrder(0, -1)
    preOrder(0, -1)
    return dp
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

Explanation: The Go implementation mirrors the Python logic, using slices and a helper max function. The adjacency list is built using slices, and recursive functions handle post-order and pre-order traversals. The key difference is syntax and explicit handling of slices versus Python lists.

Worked Examples

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

Node	Subtree max	Parent contribution	Final dp
0	1	0	1
1	0	+1 (from 0 and 2)	1
2	1	0	1

Output: [1,1,1]

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

Node	Subtree max	Parent contribution	Final dp
0	-1	+3	2
1	2	+1	3
2	-1	+3	2
3	2	+1	3
4	1	+2	3

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

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Each node and edge is visited a constant number of times in the two DFS traversals
Space	O(n)	Adjacency list, DP array, and recursion stack

Since we only traverse each edge twice and use linear auxiliary storage, the algorithm scales efficiently to the problem constraints.

Test Cases

# Provided examples
assert Solution().maxSubgraphScore(3, [[0,1],[1,2]], [1,0,1]) == [1,1,1]  # Example 1
assert Solution().maxSubgraphScore(5, [[1,0],[1,2],[1,3],[3,4]], [0,1,0,1,1]) == [2,3,