ParenthesesTree | Topcoder Archive

Problem Statement

Correct parentheses sequences can be defined recursively as follows:

The empty string "" is a correct sequence.
If "X" and "Y" are correct sequences, then "XY" (the concatenation of X and Y) is a correct sequence.
If "X" is a correct sequence, then "(X)" is a correct sequence.
Each correct parentheses sequence can be derived using the above rules.

Examples of correct parentheses sequences include "", "()", "()()()", "(()())", and "(((())))".

We have a rooted tree with n vertices. The vertices are labeled 0 through n-1. For each vertex v, the parent of v has a smaller number than v. (Hence, vertex 0 is the root: the only vertex with no parent.)

You are given the description of the tree: the int[] p with n-1 elements. For each valid i, vertex p[i] is the parent of vertex (i+1).

You are required to place a single parenthesis onto each edge of the tree. Once you do that, each walk on our tree will produce a sequence of parentheses. Note that the direction of walking will matter. For example, if the edge (x,y) has a label that reads '(' when we go from x to y, the same label reads ')' when we go from y to x.

Different labels may have different costs. You are given these costs in the int[]s L and R. For each valid i:

Using the label that reads '(' when we go from p[i] to (i+1) costs L[i].
Using the label that reads ')' when we go from p[i] to (i+1) costs R[i].

Note that you cannot leave an edge unlabeled, you must always choose one of the two available labels.

Finally, you are given a set of constraints. These are given in the int[]s a and b. For each valid i, consider the unique simple path from the vertex a[i] to the vertex b[i] in our tree. The string we'll read along this path must be a valid parentheses sequence.

Compute and return the minimal cost of choosing the n-1 labels in such a way that all constraints are satisfied. If it is impossible to satisfy all constraints, return -1 instead.

Definition

Class:: ParenthesesTree
Method:: minCost
Parameters:: int[], int[], int[], int[], int[]
Returns:: int
Method signature:: int minCost(int[] p, int[] L, int[] R, int[] a, int[] b)
(be sure your method is public)

Constraints

n will be between 2 and 50, inclusive.
p, L and R will contain exactly n-1 elements.
For each valid i, 0 <= p[i] <= i.
Each element in L and R will be between 1 and 1,000, inclusive.
a will contain between 1 and 50 elements, inclusive.
a and b will contain the same number of elements.
Each element in a and b will be between 0 and n-1, inclusive.

Examples

```
{0,1,2,3}
```
```
{1,2,3,4}
```
```
{10,20,30,40}
```
```
{0}
```
```
{4}
```
```
Returns: 64
```
There are 2 valid solutions: 0-(-1-(-2-)-3-)-4 0-(-1-)-2-(-3-)-4 In the first one, the cost is 1 + 2 + 30 + 40 = 73. In the second one, the cost is 1 + 20 + 3 + 40 = 64. So we should return 64.
```
{0,1,2,3}
```
```
{1,2,3,4}
```
```
{10,20,30,40}
```
```
{0}
```
```
{3}
```
```
Returns: -1
```
When we read from 0 to 3 we will get a string with 3 characters and that can't be a valid parentheses sequence. So there is no solution.

{0,1,2,3}

{1,2,3,4}

{10,20,30,40}

{2}

{2}

Returns: 10

{0,1,1,3,4,4}

{1,2,3,4,5,6}

{100,200,300,400,500,600}

{0,0,2,2,1}

{5,6,5,6,4}

Returns: 1704

{0,1,1,3,4,4}

{1,2,3,4,5,6}

{100,200,300,400,500,600}

{0,0,2,2}

{5,6,5,6}

Returns: 1605

{0, 0, 2, 0, 2, 3, 1, 5, 8, 2, 1, 6, 5, 5, 10, 11, 8, 12, 1}

{959, 475, 349, 884, 853, 73, 883, 737, 910, 435, 207, 1, 484, 490, 485, 968, 19, 428, 648}

{899, 770, 514, 327, 626, 84, 244, 695, 669, 138, 480, 778, 368, 892, 440, 976, 957, 959, 107}

{7, 13, 13, 5, 6, 1, 7}

{10, 13, 6, 17, 4, 2, 12}

Returns: 9813

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.