Problem Statement | | | Owaski is another pet dog of Zhangzj. He likes playing on a tree.
The tree has N vertices, labeled from 0 to N - 1. You are given an int[] parent of N - 1 elements. For each i between 0 and N - 2, inclusive, there is an edge between vertex i + 1 and vertex parent[i]. In a single step, Owaski can walk from a vertex to one of its adjacent vertices. You are given an int[] pleasure, element i of which indicates the pleasure Owaski gets when he reaches vertex i. Before entering the tree, his pleasure is 0. Of course, at some moments Owaski's pleasure can be negative, as some vertices can make him unhappy. However, Owaski doesn't like to be unhappy. Thus whenever his pleasure becomes negative, he will make it zero again by playing Overwatch and winning nearly every game. Owaski may enter each vertex arbitrarily many times.
However, he doesn't like old things.
Thus, if he enters a vertex he visited before, his pleasure remains unchanged.
In other words, each vertex only influences Owaski's pleasure when he visits it for the first time.
Owaski enters the tree at vertex 0 (therefore the pleasure of vertex 0 also counts), and can leave the tree whenever he wants. Since all dogs love to be happy, he wants to leave with as much pleasure as possible. Return the maximal pleasure he can get. | | | Definition | | | | Class: | OwaskiAndTree | | Method: | maximalScore | | Parameters: | int[], int[] | | Returns: | int | | Method signature: | int maximalScore(int[] parent, int[] pleasure) | | (be sure your method is public) |
| | | | | | Constraints | | - | N will be between 1 and 1,000, inclusive. | | - | parent will contain exactly N - 1 elements. | | - | pleasure will contain exactly N elements. | | - | For each i, parent[i] will be between 0 and i, inclusive. | | - | Each element of pleasure will be between -1,000,000 and 1,000,000, inclusive. | | | Examples | | 0) | | | | {0, 1, 2, 3, 4, 5, 6, 7, 8} | {1, 1, -1, -1, -1, -1, 1, 1, 1, 1} |
| Returns: 4 | | The tree forms a chain of 10 vertices and 9 edges. The optimal way is to walk through the chain. The values of pleasure of Owaski after visiting vertex 0 to 9 are 1, 2, 1, 0, 0, 0, 1, 2, 3, 4, respectively. He can leave the tree after that, yielding net pleasure of 4. |
|
| | 1) | | | | {0, 0, 1, 2} | {2, 3, 4, -1, -1} |
| Returns: 9 | | This time his path can be 0 → 1 → 0 → 2. Note that although Owaski visits 0 twice, the pleasure of that vertex only counts once. |
|
| | 2) | | | | {0, 0, 1, 1, 2, 2, 5, 5} | {1, 2, -3, -7, 3, 2, 7, -1, 3} |
| Returns: 17 | | One of the optimal paths is 0 → 2 → 5 → 8 → 5 → 2 → 6 → 2 → 0 → 1 → 4. |
|
| | 3) | | | | {0, 1, 1, 1, 0, 3, 1, 3, 4, 4, 3, 6, 8, 0, 12, 12, 11, 7, 7} | {-154011, 249645, 387572, 292156, -798388, 560085, -261135, -812756, 191481, -165204, 81513, -448791, 608073, 354614, -455750, 325999, 227225, -696501, 904692, -297238} |
| Returns: 3672275 | |
| | 4) | | | | |
This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2024, TopCoder, Inc. All rights reserved.
|
