Given a tree (not a binary tree), where each node in the tree has an integer value. You are required to find the maximum sum for values of nodes under the constraint that the sum cannot contain both a node and its parent node. Describe an algorithm that maximizes the sum of values of the selected nodes in the tree.

Hint: the node structure will hold a vector of node pointers representing the children and two additional integers; one for the value and another for the index of the node and a pointer to parent node (optional).

You are required to answer the question above using dynamic programming.(c++ code)

Input Format

• The first line will contain the number of nodes in the tree N.
• The following N space-separated numbers will contain the data in each node.
• The following N-1 lines represents edges and will contain 2 values each:
• • Index of the parent.
• • Index of the child.

Constraints

• 1 N 10^5
• For each value vi: 1 vi 10^8

Output Format

The sum of values of the selected nodes.

Output Format The sum of values of the selected nodes. Sample Input o 8 4 2 3 60 4 15 5 10 0 1 02 03 l 4 1 5 36 37 Sample Output 0 82 Explanation 0 The selected nodes to maximize the sum are highlighted in the following figure. 4 2 3 60 4 15 5 10