JOIN
Get Time

   Problem Statement  

 Problem Statement for FoxMeeting

Problem Statement

    

Foxland is a country with n cities. The cities are numbered 1 through n. The road network in Foxland is a tree. You are given the description of the roads: three int[]s A, B and L with n-1 elements each. For each valid i, there is a bidirectional road connecting the cities A[i] and B[i], and the length of the road is L[i].

There are some foxes in Foxland. Each fox lives in a different city. You are given a int[] foxes. The elements of foxes are the numbers of cities inhabited by foxes.

The foxes are running a secret candy-smuggling network. Recently they have been harrassed by a new strict police officer: cat Taro. In order to avoid him, the foxes have now learned to communicate by waving their tails at each other. However, two foxes can only communicate in this way if they see each other. More precisely, they must either both be in the same city, or they have to be in two adjacent cities. (Adjacent cities are cities directly connected by a road, regardless of the road's length.)

Foxes can forward messages to other foxes, which makes communication transitive: If fox x can talk to fox y and fox y can talk to fox z, fox x will be able to communicate with fox z as well.

In order to avoid Taro, each fox must be able to talk to all other foxes (either directly or indirectly). If it isn't possible in their current configuration, some foxes may be forced to move into different cities. The foxes think that it is also suspicious if a fox moves too far from its current home. Therefore, they want to minimize the maximum distance traveled by any fox.

Formally, find and return the smallest integer D with the following property: It is possible to relocate some (possibly zero, possibly all) of the foxes into new cities in such a way that:

  • For each fox, the total total distance traveled by that fox is at most D.
  • After the relocation, all foxes can communicate (either directly or indirectly).

 

Definition

    
Class:FoxMeeting
Method:maxDistance
Parameters:int[], int[], int[], int[]
Returns:int
Method signature:int maxDistance(int[] A, int[] B, int[] L, int[] foxes)
(be sure your method is public)
    
 

Constraints

-n will be between 1 and 50, inclusive.
-A, B, and L will contain exactly n-1 elements each.
-Each element in A and B will be between 1 and n, inclusive.
-Each element in L will be between 1 and 100,000, inclusive.
-A, B, and L will define a tree.
-Number of elements in foxes will be between 1 and n, inclusive.
-Each element in foxes will be between 1 and n, inclusive.
-All the elements of foxes are distinct.
 

Examples

0)
    
{1}
{2}
{5}
{1, 2}
Returns: 0
There are two cities connected by a single road of length 5. There are two foxes: one in each city. As they are in adjacent cities, they can already communicate so no relocation is necessary.
1)
    
{1, 2}
{2, 3}
{1, 1}
{1, 3}
Returns: 1
This country has three cities and two roads: 1-2 (length 1) and 2-3 (length 1). Initially, there is one fox in city 1 and another fox in city 3. In one optimal solution, the first fox will move from city 1 to city 2. In another optimal solution, both foxes will move from their respective cities to city 2. In each of the solutions described above we have D = 1.
2)
    
{1, 2}
{2, 3}
{1, 1}
{1, 2, 3}
Returns: 0
No relocation is necessary, all foxes can already talk to each other.
3)
    
{10,8,3,7,2,6,9,1,4}
{5,5,8,10,5,5,6,10,3}
{71846,10951,42265,37832,29439,95676,83661,28186,21216}
{1,2,3,4,5,6,7,8,9,10}
Returns: 0
4)
    
{8,15,22,24,2,25,13,26,18,4,9,29,1,12,3,16,14,21,19,27,17,7,20,10,30,11,6,5,23}
{28,28,8,8,28,28,25,2,13,24,24,22,22,29,4,22,8,4,1,24,21,14,18,16,13,21,14,1,25}
{79374,40629,43195,73589,24200,63937,35339,7598,65109,51764,11142,84017,51078,58051,81387,22035,34883,92710,52283,57337,79309,3383,41904,35839,38242,43208,82062,24676,71838}
{3,5,7,9,10,14,17,19,20,21,24,25,28}
Returns: 107013
5)
    
{34,14,22,9,24,19,11,37,33,21,5,30,1,43,7,31,45,27,6,12,13,35,23,47,49,50,26,40,16,10,48,25,29,15,28,46,4,20,44,17,39,32,38,2,42,8,36,3,41}
{18,18,18,14,9,34,9,24,34,11,18,14,21,21,43,1,22,7,1,30,14,33,13,18,9,5,1,1,26,19,50,33,50,40,29,48,50,37,16,40,48,14,30,22,47,37,7,50,6}
{22051,11109,85275,6691,43705,47374,27748,5411,62549,84079,89542,38006,82198,24083,16847,66335,3542,72495,37378,73973,85703,51682,68688,94295,31337,
90071,99317,63484,43244,99079,55857,34503,79709,82140,91137,27033,91599,61168,52345,49569,58919,38133,43361,
40718,2115,79278,88841,40966,42023}
{5,12,13,18,23,27,28,29,32,33,34,35,36,37,40,42,43,47,48,49,50}
Returns: 89342

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:
       2015 TopCoder Open Algorithm Round 2A - Division I, Level Two