Skip to content
Hello Python

Choose Non-Adjacent Tree Values

Practice ExerciseIntermediateMediumTree DPTree

Checking your account…

Sign in to save your code and progress across devices. The lesson and problem statement remain public.

Loading the interactive Practice workspace.If it does not appear, the problem and learning material remain readable, but browser execution is unavailable.Reload Practice workspace

Problem

Implement maximum_tree_independent_sum(parents, values). Node 0 is the root, parents[0] is -1, and parents[i] is the parent of i. Choose node values with no parent-child pair both chosen and return the maximum sum. Values are nonnegative.

Starter code

def maximum_tree_independent_sum(parents, values):
    pass
Test cases

branching-tree

{
  "args": [
    [
      -1,
      0,
      0,
      1,
      1
    ],
    [
      4,
      2,
      3,
      5,
      1
    ]
  ]
}

Expected: 10

chain-tree

{
  "args": [
    [
      -1,
      0,
      1,
      2
    ],
    [
      2,
      7,
      4,
      6
    ]
  ]
}

Expected: 13

Wizard outline
  1. Step 1: Build child relationships

    Turn parent indexes into a traversable rooted tree. Bottom-up states require visiting every child before its parent.

  2. Step 2: Return take and skip states

    Compute both legal outcomes for a root and its direct children. Taking a parent forces every child skip, while skipping it allows the better child state.

  3. Step 3: Combine decisions through depth

    Complete the recurrence for chains and branching trees. Each returned pair summarizes all legal choices below the node without exposing internal structure to its parent.

Footguns and prerequisites
  • Taking a node requires skipping every child, not merely one child.
  • Using a single subtree total loses the state needed by the parent.
  • dynamic programming
Reviewed references
Recommended approach and implementation

Build child adjacency and return the optimal take and skip totals from each subtree.

Why it works: When a node is taken, every child must be skipped; when it is skipped, each child independently chooses its better valid state. These cases partition all legal selections, so the better root state is globally optimal.

def maximum_tree_independent_sum(parents, values):
    if not values:
        return 0
    children = [[] for _ in values]
    for node in range(1, len(values)):
        children[parents[node]].append(node)
    def solve(node):
        take = values[node]
        skip = 0
        for child in children[node]:
            child_take, child_skip = solve(child)
            take += child_skip
            skip += max(child_take, child_skip)
        return take, skip
    return max(solve(0))