Problem Description

You are given an undirected tree with n nodes labeled from 0 to n - 1, rooted at node 0. The tree structure is defined by a 2D integer array edges of length n - 1, where edges[i] = [ai, bi] indicates an edge between nodes ai and bi.

Each node i has an associated value given by values[i], where values is a 0-indexed integer array of length n.

You start with a score of 0. You can perform the following operation any number of times:

• Pick any node i
• Add values[i] to your score
• Set values[i] to 0

A tree is considered healthy if the sum of values on every path from the root node to any leaf node is different from zero (i.e., not equal to zero).

Your task is to find the maximum score you can obtain by performing these operations while ensuring the tree remains healthy throughout.

In other words, you need to select nodes to add to your score such that:

1. You maximize the total score (sum of selected node values)
2. After setting selected nodes' values to 0, every root-to-leaf path still has a non-zero sum

This means on every path from root to leaf, at least one node must remain unselected (keep its original value) to maintain the healthy property of the tree.

Flowchart Walkthrough

First, let's pin down the algorithm using the Flowchart. Here's a step-by-step walkthrough:

Is it a graph?

• Yes: The problem involves nodes (labeled 0 to n-1) and edges that form an undirected tree structure.

Is it a tree?

• Yes: The problem explicitly states we have an undirected tree with n nodes, where there are exactly n-1 edges connecting the nodes, and it's rooted at node 0.

DFS

• Yes: Since we identified this as a tree problem, the flowchart leads us directly to DFS (Depth-First Search).

Conclusion: The flowchart suggests using a DFS approach for this problem.

This makes sense because:

1. We need to traverse the tree from root to leaves to ensure every path maintains the "healthy" property
2. We need to make decisions at each node about whether to select it or not
3. The problem requires considering the relationship between parent and child nodes (decisions at parent nodes affect constraints on child nodes)
4. Tree DP with DFS allows us to compute optimal solutions for subtrees and combine them to get the overall optimal solution

The DFS approach enables us to:

• Traverse each subtree recursively
• Calculate two states for each node: total sum of subtree values, and maximum score while keeping the tree healthy
• Make optimal decisions about which nodes to select based on information from child subtrees

Intuition

Let's think about what we're trying to achieve. We want to maximize our score by selecting nodes, but we have a constraint: every path from root to leaf must have at least one node that we don't select (to keep the tree "healthy").

This is essentially asking: what's the maximum sum of nodes we can take while leaving at least one node untouched on every root-to-leaf path?

We can reframe this problem: instead of thinking about which nodes to select, think about which nodes to leave behind. Since we must leave at least one node on each path, we want to minimize the sum of nodes we leave behind. The maximum score would then be (total sum of all nodes) - (minimum sum of nodes to leave behind).

For each subtree rooted at node i, we need to track two pieces of information:

1. The total sum of all nodes in this subtree
2. The minimum cost to keep this subtree healthy (minimum sum of nodes we must leave unselected)

When we're at a node i with children, we have two choices:

• Leave node i unselected: If we don't select node i, then all paths through this node already have one unselected node (node i itself). This means we can freely select all nodes in the child subtrees. The cost is values[i].
• Select node i: If we select node i, then each child subtree must maintain the healthy property on its own. The cost is the sum of minimum costs from all child subtrees.

We want the minimum between these two options.

For leaf nodes, the situation is special. If we're at a leaf, we must leave it unselected (cost = values[leaf]) because there's no child to rely on for maintaining the healthy property.

The DFS naturally handles this recursive structure: we compute the optimal solution for each subtree bottom-up, combining child results to determine the parent's optimal strategy.

The final answer is the maximum score we can achieve for the entire tree rooted at node 0, which equals (total sum) - (minimum to leave behind), but the solution directly computes the maximum we can take.

Learn more about Tree, Depth-First Search and Dynamic Programming patterns.

Solution Approach

The solution uses Tree Dynamic Programming with DFS to solve this problem efficiently. Let's walk through the implementation step by step.

Data Structure Setup: First, we build an adjacency list representation of the tree from the edges array:

g = [[] for _ in range(len(values))]
for a, b in edges:
    g[a].append(b)
    g[b].append(a)

DFS Function Design: The core of the solution is the dfs(i, fa) function where:

• i is the current node being processed
• fa is the parent node (used to avoid revisiting the parent in an undirected tree)

The function returns a tuple (a, b) where:

• a: Total sum of all node values in the subtree rooted at i
• b: Maximum score achievable from the subtree while keeping it healthy

Processing Each Node:

def dfs(i: int, fa: int = -1) -> (int, int):
    a = b = 0
    leaf = True
    for j in g[i]:
        if j != fa:
            leaf = False
            aa, bb = dfs(j, i)
            a += aa
            b += bb

For each node, we:

1. Initialize accumulators a and b for collecting child subtree results
2. Check if the current node is a leaf (has no children except its parent)
3. Recursively process all children, accumulating their results

Handling Leaf Nodes:

if leaf:
    return values[i], 0

For a leaf node:

• The total sum is just its own value
• The maximum score is 0 because we cannot select the leaf (it must remain to keep the path healthy)

Handling Internal Nodes:

return values[i] + a, max(values[i] + b, a)

For internal nodes, we return:

• First value: values[i] + a - total sum of the subtree (current node value plus sum of all child subtrees)
• Second value: max(values[i] + b, a) - the maximum of two strategies:
  • values[i] + b: Don't select current node i, but optimally select from children (cost is values[i] plus the optimal selections from children)
  • a: Select current node i, which means we can select everything from child subtrees except what's needed to keep them healthy

Final Answer:

return dfs(0)[1]

We call dfs(0) starting from the root and return the second value, which represents the maximum score achievable while keeping the tree healthy.

The algorithm runs in O(n) time as we visit each node exactly once, and uses O(n) space for the recursion stack and adjacency list.

Example Walkthrough

Let's walk through a small example to illustrate the solution approach.

Consider a tree with 4 nodes and the following structure:

    0 (value=5)
   / \
  1   2
(3)  (4)
 |
 3
(2)

• Node 0 has value 5
• Node 1 has value 3
• Node 2 has value 4
• Node 3 has value 2
• Edges: [[0,1], [0,2], [1,3]]

Step 1: Build adjacency list

g[0] = [1, 2]
g[1] = [0, 3]
g[2] = [0]
g[3] = [1]

Step 2: DFS traversal starting from root (node 0)

We'll process the tree bottom-up, starting with the leaves.

Processing Node 3 (leaf):

• dfs(3, parent=1)
• Node 3 is a leaf
• Returns (2, 0) - total sum is 2, max score is 0 (can't select leaf)

Processing Node 2 (leaf):

• dfs(2, parent=0)
• Node 2 is a leaf
• Returns (4, 0) - total sum is 4, max score is 0 (can't select leaf)

Processing Node 1 (internal node):

• dfs(1, parent=0)
• Has child node 3, which returned (2, 0)
• Accumulate: a = 2 (sum from child), b = 0 (max score from child)
• Not a leaf, so return:
  • Total sum: values[1] + a = 3 + 2 = 5
  • Max score: max(values[1] + b, a) = max(3 + 0, 2) = 3
  • Returns (5, 3)

This means for the subtree rooted at node 1:

• Strategy 1: Don't select node 1 (value=3), select optimally from children (score=0) → total score = 0
• Strategy 2: Select node 1, which forces us to leave at least one node in child subtree unselected → we can take node 1 (value=3) but must leave node 3 (value=2) → score = 3
• We choose the maximum: 3

Processing Node 0 (root):

• dfs(0, parent=-1)
• Has children nodes 1 and 2
  • Node 1 returned (5, 3)
  • Node 2 returned (4, 0)
• Accumulate: a = 5 + 4 = 9, b = 3 + 0 = 3
• Not a leaf, so return:
  • Total sum: values[0] + a = 5 + 9 = 14
  • Max score: max(values[0] + b, a) = max(5 + 3, 9) = 9
  • Returns (14, 9)

This means for the entire tree:

• Strategy 1: Don't select root node 0 (value=5), select optimally from children → score = 3 (from subtree 1) + 0 (from subtree 2) = 3
• Strategy 2: Select root node 0 → we can take everything except what's minimally needed in each subtree:
  • From left subtree (nodes 1,3): can take value 3 (leaving node 3)
  • From right subtree (node 2): can't take anything (it's a leaf)
  • Total: 5 (root) + 3 (node 1) + 0 = 8

Wait, let me recalculate the root node processing:

When we select node 0, we need each child subtree to maintain healthiness independently. The formula max(values[0] + b, a) compares:

• values[0] + b = 5 + 3 = 8: Keep node 0 unselected, take optimal from children
• a = 9: Select node 0, which means we can take all child values except minimum needed for health

Actually, the second interpretation needs clarification. When we compute a (select current node), it represents taking everything from child subtrees. Since we must maintain health, the actual score would be the total sum minus what we must leave.

The final answer is 9, which represents:

• Selecting nodes 0, 1, and 2 (total value = 5 + 3 + 4 = 12)
• But we must leave node 3 unselected to maintain the path 0→1→3 as healthy
• Wait, that gives us 12, not 9...

Let me reconsider the formula. The max(values[i] + b, a) actually means:

• Option 1: Don't take node i (cost = values[i]), but take optimal from children (gain = b)
• Option 2: Take node i and everything possible from children (gain = a)

Since the problem asks for maximum score we can obtain, the answer of 9 means we can select nodes with total value 9, leaving some nodes unselected to maintain health. The optimal selection would be nodes 1, 2, and 2 (values 3 + 4 + 2 = 9), leaving node 0 unselected to keep all paths healthy.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n)

The algorithm performs a depth-first search (DFS) traversal of the tree. Each node is visited exactly once during the DFS traversal. For each node, the algorithm performs constant-time operations (calculating values, comparing maximum) and iterates through its adjacent nodes. Since this is a tree structure with n nodes, there are exactly n-1 edges, meaning each edge is traversed twice (once from each direction). Therefore, the total time complexity is O(n + 2(n-1)) = O(n).

Space Complexity: O(n)

The space complexity consists of several components:

• The adjacency list g requires O(n) space to store all nodes and their connections
• The recursive DFS call stack can go as deep as the height of the tree, which in the worst case (a skewed tree) is O(n)
• Each recursive call uses O(1) additional space for local variables (a, b, leaf, aa, bb)

Therefore, the overall space complexity is O(n).

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Incorrectly Handling the Two Choice Strategies

Pitfall: A common mistake is misunderstanding what the two choices at each internal node represent. Many developers incorrectly think:

• Choice 1: Select the current node (add it to score)
• Choice 2: Don't select the current node

This leads to incorrect formulations like:

# WRONG interpretation
max_score = max(
    values[node] + subtree_sum,  # Select current node
    max_score_from_children       # Don't select current node
)

Why it's wrong: When you select a node (set its value to 0), you're removing it from the path sum calculation. The actual choices are:

• Keep the current node (don't select it): You can then select ALL values from child subtrees
• Remove the current node (select it): You must keep at least one node in each child's path to maintain health

Correct Implementation:

max_achievable_score = max(
    values[node] + max_score_from_children,  # Remove current (select it)
    subtree_sum  # Keep current (don't select it)
)

2. Forgetting to Track Whether a Node is a Leaf

Pitfall: Treating all nodes uniformly without special handling for leaf nodes:

# WRONG - doesn't handle leaves specially
def dfs(node, parent):
    subtree_sum = 0
    max_score = 0
  
    for child in adjacency_list[node]:
        if child != parent:
            child_sum, child_score = dfs(child, node)
            subtree_sum += child_sum
            max_score += child_score
  
    # Missing leaf node check!
    return values[node] + subtree_sum, max(values[node] + max_score, subtree_sum)

Why it's wrong: Leaf nodes MUST keep their values to ensure the path from root to leaf has a non-zero sum. Without this check, the algorithm might select all nodes on a path, making the sum zero.

Correct Implementation:

is_leaf = True
for neighbor in adjacency_list[node]:
    if neighbor != parent:
        is_leaf = False
        # ... process children

if is_leaf:
    return values[node], 0  # Leaf cannot contribute to score

3. Confusion Between Return Values

Pitfall: Mixing up what each return value represents or using them incorrectly:

# WRONG - returning values in wrong order or using wrong value
def dfs(node, parent):
    # ... processing ...
    return max_score, total_sum  # Wrong order!

# Or at the root:
total, score = dfs(0)
return total  # Wrong! Should return score

Correct Implementation: Always maintain consistent return value semantics:

• First value: Total sum of subtree (including current node)
• Second value: Maximum score achievable from subtree

return total_subtree_value, max_achievable_score
# And at root:
_, maximum_score = dfs(0)
return maximum_score

4. Edge Case: Single Node Tree

Pitfall: Not handling the case where the tree has only one node (which is both root and leaf):

# Potential issue if not handled correctly
edges = []
values = [5]

Solution: The algorithm naturally handles this because a single node is detected as a leaf, returning (values[0], 0), which correctly gives a maximum score of 0 (since we cannot select the only node without making the tree unhealthy).

5. Building Graph Incorrectly for Undirected Tree

Pitfall: Forgetting to add edges in both directions:

# WRONG - only adds one direction
for a, b in edges:
    adjacency_list[a].append(b)  # Missing reverse edge!

Correct Implementation:

for node_a, node_b in edges:
    adjacency_list[node_a].append(node_b)
    adjacency_list[node_b].append(node_a)

This ensures proper traversal in an undirected tree where we can move from parent to child and vice versa.