Tree Robber (DP on Trees)

You are given a tree with n nodes (0-indexed). Each node i has value values[i]. You cannot take two adjacent nodes.

Return the maximum total value you can take.

Function signature

func TreeRobber(values []int, edges [][]int) int

Example

values = [3,2,3,3,1]
edges = [[0,1],[0,2],[1,3],[1,4]]
output = 7

Constraints

• 0 <= len(values) <= 200_000
• len(edges) = max(0, len(values) - 1)
• 0 <= u, v < len(values)
• values[i] can be negative or positive

Notes

• Tree DP with take/skip states solves this in O(n).