Maximum Weight Set With No Ancestor Pairs

You are given an integer n, a list edges where each edges[i] = [parent, child] describes one directed edge of a rooted tree on nodes 0 to n - 1 with root 0, and an integer array weights where weights[i] is the weight of node i.

A node u is an ancestor of a node v if u lies on the path from the root to v and u is not v itself.

Choose a subset of nodes so that no chosen node is an ancestor of another chosen node. Return the maximum possible total weight of the chosen nodes.

Examples

Example 1

Input: n = 6, edges = [[0,1],[0,2],[1,3],[1,4],[2,5]], weights = [10,5,6,20,3,15]
Output: 38
Explanation: Choosing nodes 3, 4, and 5 gives weight 20 + 3 + 15 = 38, and none of them is an ancestor of another since they sit in different branches. Choosing node 0 together with any other node is invalid because node 0 is an ancestor of every other node, and no combination scores higher than 38.

Example 2

Input: n = 1, edges = [], weights = [7]
Output: 7
Explanation: The only node is the root, so choosing it alone is the only option.

Example 3

Input: n = 3, edges = [[0,1],[0,2]], weights = [100,1,1]
Output: 100
Explanation: Choosing both leaves gives 1 + 1 = 2, but choosing just the root gives 100, which is larger. Choosing the root together with a leaf is invalid because the root is an ancestor of both leaves.