Compute maximum sum in a tree without adjacency
Overview
This question evaluates dynamic programming on trees and graph component identification by requiring selection of non-adjacent nodes to maximize a sum, targeting skills in tree algorithms, constraint-based optimization, and rigorous correctness and complexity reasoning.
Given a tree where each node has an integer value, select a subset of nodes to maximize the sum under the constraint that if you choose a node, you cannot choose any of its children (i.e., no parent–child pair can both be chosen). Implement a function that returns the maximum achievable sum. Describe your algorithm, justify correctness, and analyze time and space complexity. Follow-up: How would you handle a forest (multiple disconnected trees)? Explain how you would identify components and compute the overall result.