JOIN
Get Time

   Problem Statement  

 Problem Statement for FoxConnection

Problem Statement

    There are N cities in Treeland. The cities are numbered 1 through N. The roads in Treeland have the topology of a tree. That is, there are exactly N-1 bidirectional roads in Treeland, each connecting a pair of cities, and it is possible to travel between any two cities along the roads. For the purpose of this problem, all roads have the same length, and this length is our unit of distance.



You are given two int[]s A and B that describe the tree. Each of these int[]s has N-1 elements. For each valid i, there is a road that connects the cities A[i] and B[i].



There are some foxes in Treeland. Currently, each of the foxes lives in a different city. You are given a String haveFox with N characters. For each i, character i of haveFox is 'Y' if there is a fox in city i+1, or 'N' otherwise.



The foxes would like to live closer to each other. To achieve that, some foxes (possibly all of them or none at all) will move to different cities. There are three constraints for the move:
  1. After the foxes move, there must again be at most one fox in each city. (There are no restrictions on how the foxes travel while they are moving.)
  2. After the foxes move, the set of cities inhabited by the foxes must be connected. That is, for any two different cities i and j that both contain a fox, all the cities on the (only) path between i and j must also contain a fox.
  3. The total distance traveled by the foxes during the move must be as small as possible.




Return the smallest possible sum of distances traveled by the foxes.
 

Definition

    
Class:FoxConnection
Method:minimalDistance
Parameters:int[], int[], String
Returns:int
Method signature:int minimalDistance(int[] A, int[] B, String haveFox)
(be sure your method is public)
    
 

Constraints

-N will be between 2 and 50, inclusive.
-A will contain exactly N-1 elements.
-Each element of A will be between 1 and N, inclusive.
-B will contain exactly N-1 elements.
-Each element of B will be between 1 and N, inclusive.
-The graph described by A and B will be a tree.
-haveFox will contain exactly N characters.
-Each character in haveFox will be either 'Y' or 'N'.
 

Examples

0)
    
{1,2,3}
{2,3,4}
"YNNY"
Returns: 2
Treeland looks as follows: 1-2-3-4. Two foxes are located in city 1 and city 4. One optimal solution is:
  • The fox located in city 1 moves to city 2.
  • The fox located in city 4 moves to city 3.
1)
    
{1,1,1,1}
{2,3,4,5}
"NYYYY"
Returns: 1
We can move any one of the foxes to city 1. After that the cities with foxes will form a connected set.
2)
    
{1,3,4,5,4}
{2,2,2,4,6}
"YNYNYY"
Returns: 2
3)
    
{1,2,3,4,5,6,7,8,9}
{2,3,4,5,6,7,8,9,10}
"YNNNYNYNNY"
Returns: 7
4)
    
{1,2,3,4,3,6,8,7}
{2,3,4,5,6,8,9,6}
"YNNYYNYYY"
Returns: 3
5)
    
{1}
{2}
"NY"
Returns: 0
There can be only 1 fox.
6)
    
{1}
{2}
"NN"
Returns: 0
And there can be no foxes.

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)2010, TopCoder, Inc. All rights reserved.

This problem was used for:
       Single Round Match 604 Round 1 - Division I, Level Two