961. Maximum Weight Independent Set on a Tree

Given a tree with n nodes labeled 0..n-1 (rooted at 0), an undirected edge list, and an array of node weights, choose a subset of nodes with no two adjacent (an independent set) maximizing the total weight. Return that maximum weight. The input is JSON {n, edges, weights}.

Input: JSON {n, edges, weights}.

Output: Integer — the maximum independent-set weight.

Examples

Input: {"n":5,"edges":[[0,1],[0,2],[1,3],[1,4]],"weights":[3,2,1,10,5]}
Output: 18
Explanation: Choose nodes 0, 3, 4 (and skip 1,2).

Input: {"n":1,"edges":[],"weights":[7]}
Output: 7
Explanation: Single node.

Input: {"n":3,"edges":[[0,1],[0,2]],"weights":[1,2,3]}
Output: 5
Explanation: Choose the two leaves.

Constraints

• 1<=n<=10^5
• 0<=weight<=10^4
• edges form a tree

Asked by