PreviousNext
Coding/Dynamic programming

Maximum weight independent set tree

Write codeMedium30 minGoogle style

Your task

You are given a tree with n nodes (0-indexed) as an edge list, and a value array val. Choose a subset of nodes with maximum total value such that no two chosen nodes are adjacent (an independent set). The tree is rooted at node 0. Return the maximum achievable sum. 1 <= n <= 2000, 0 <= val[i] <= 10^4, edges has n-1 entries.

Examples

tree_max_independent(n: int, edges: list[list[int]], val: list[int]) -> int
Example 1
Inputtree_max_independent(3, [[0, 1], [0, 2]], [1, 2, 3])
Output5