You are given an integer array parent of length n representing a rooted tree with nodes labeled from 0 to n - 1, where parent[i] denotes the parent of node i. The tree is rooted at node 0, so parent[0] = -1.
You are also given two integer arrays op and score, both of length n, where op[i] determines the operation allowed at node i, and score[i] represents its score.
You need to process each non- node i according to the following rules:
- If
op[i] = 0, you can choose at most one child of nodeiand set the scores of all nodes in that child's to 0. - If
op[i] = 1, you must choose exactly one child of nodeiand set the scores of all nodes in that child's subtree to 0.
Each non-leaf node must be processed exactly once. You may process the nodes in any order.
Return the maximum possible sum of the scores after performing the operations.
Example 1:
Input: parent = [-1,0,0,0,1,2,3,3], op = [1,1,0,0,1,1,0,1], score = [5,6,1,2,3,2,3,-3]
Output: 16
Explanation:
One optimal way is to process the nodes in the following order:
- Nodes 4, 5, 6, and 7: They are leaf nodes, so no operations are performed on them.
- Node 1: Since
op[1] = 1, we must select one of its children. Choose node 4, setting the scores of all nodes in its subtree (node 4) to 0. - Node 2: Since
op[2] = 0, we may choose a child or do nothing. For this node, we do nothing. - Node 3: Since
op[3] = 0, we may choose a child or do nothing. Choose node 7, setting the scores of all nodes in its subtree (node 7) to 0. - Node 0: Since
op[0] = 1, we must select one of its children. Choose node 2, setting the scores of all nodes in its subtree (nodes 2 and 5) to 0.
After performing these operations, the scores are [5, 6, 0, 2, 0, 0, 3, 0], giving a total sum of 16.
No valid sequence of operations can produce a larger sum. Therefore, the answer is 16.
Example 2:
Input: parent = [-1,0,0], op = [0,0,0], score = [1,2,3]
Output: 6
Explanation:
- We only need to process node 0, since node 1 and node 2 are leaves.
- Since
op[0] = 0, we can choose to do nothing. - Therefore, all scores are preserved, giving the maximum possible sum of 6.
Example 3:
Input: parent = [-1], op = [1], score = [-10]
Output: -10
Explanation:
- The only node in the tree is a leaf, so we can't process any node.
- Therefore, the maximum possible score sum is -10.
Constraints:
1 <= n <= 105n == parent.length == op.length == score.lengthparent[0] == -10 <= parent[i] <= n - 1for alliin[1, n - 1]0 <= op[i] <= 1-104 <= score[i] <= 104- The input is generated such that the array
parentrepresents a valid tree rooted at node 0.