DragonSlaying | Topcoder Archive

Problem Statement

You are fighting a dragon with several heads. The dragon has an unusual neck structure. Each neck ends in a head. However, not all necks begin at the dragon's shoulders. Instead, some necks begin at other heads of the dragon. Thus, the dragon has the shape of a tree.
Different necks may have a different thickness and thus a different amount of effort is required if we want to cut them. You are given the description of the dragon: int[]s parent and effort with n elements each. The shoulders of the dragon have number 0, the heads are numbered 1 through n, inclusive. For each valid i, there is a neck that grows from head parent[i] to head (i+1), and the effort needed to cut it is effort[i].
Not all heads are vital for the creature. You are given the indices of all vital heads in the int[] heads. (Shoulders are never a vital head.)
You want to kill the dragon. To do that, you must cut some necks in a way that separates all vital heads from the shoulders. Compute and return the minimum total effort needed to do that.

Definition

Class:: DragonSlaying
Method:: offWithHisHeads
Parameters:: int[], int[], int[]
Returns:: int
Method signature:: int offWithHisHeads(int[] parent, int[] effort, int[] heads)
(be sure your method is public)

Constraints

parent will contain between 1 and 50 elements, inclusive.
effort will contain the same number of elements as parent.
Element i of parent will be between 0 and i, inclusive.
Each element of effort will be between 1 and 100, inclusive.
heads will contain between 1 and (the number of elements in parent) elements, inclusive.
Each element of heads will be between 1 and (the number of elements in parent), inclusive.
All elements of heads will be distinct.

Examples

```
{0, 1, 2}
```
```
{3, 2, 1}
```
```
{2}
```
```
Returns: 2
```
The heads form a chain 0 -> 1 -> 2 -> 3. There are two ways to cut off head 2: cut the neck between heads 0 and 1 (effort 3) or between heads 1 and 2 (effort 2); the second way is optimal. Note that you'll also be cutting off head 3 which is not required.
```
{0, 1, 1}
```
```
{4, 2, 1}
```
```
{3, 2}
```
```
Returns: 3
```
The necks are 0 -> 1, 1 -> 2 and 1 -> 3. There are two ways to cut off both heads 2 and 3: cut them off separately (effort 1 + 2) or cut the neck between heads 0 and 1 (effort 4); the first way is optimal.
```
{0, 1, 1, 2}
```
```
{3, 2, 2, 2}
```
```
{2, 3, 4}
```
```
Returns: 3
```
The best way to cut off heads 2, 3 and 4 is to sever the neck between 0 and 1.

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.