Statistics

Problem Statement for "Egalitarianism3Easy"

Problem Statement

In Treeland there are n cities, numbered 1 through n. The cities are linked by n-1 bidirectional roads. Each road connects a pair of cities. The roads are built in such a way that each city is reachable from each other city by roads. (In other words, the topology of the road network is a tree.)

You are given the int n and three int[]s that describe the road network: a, b, and len. For each i between 0 and n-2, inclusive, there is a road of length len[i] that connects the cities a[i] and b[i].

The distance between two cities is the sum of lengths of roads on the sequence of roads that connects them. (Note that this sequence of roads is always unique.)

You want to select k cities in such a way that all pairwise distances between the selected cities are the same. In other words, there must be a distance d such that the distance between every two selected cities is d. Return the largest possible value of k for which this is possible.

Definition

Class:
Egalitarianism3Easy
Method:
maxCities
Parameters:
int, int[], int[], int[]
Returns:
int
Method signature:
int maxCities(int n, int[] a, int[] b, int[] len)
(be sure your method is public)

Constraints

  • n will be between 1 and 10, inclusive.
  • a will contain exactly n-1 elements.
  • b will contain exactly n-1 elements.
  • len will contain exactly n-1 elements.
  • Each element in a will be between 1 and n, inclusive.
  • Each element in b will be between 1 and n, inclusive.
  • Each element in len will be between 1 and 1,000, inclusive.
  • The graph described by a and b will be a tree.

Examples

  1. 4

    {1,1,1}

    {2,3,4}

    {1,1,1}

    Returns: 3

    There are 4 cities and 3 roads, each of length 1. The roads connect the following pairs of cities: (1,2), (1,3), and (1,4). The optimal answer is k=3. We can select three cities in the required way: we select the cities {2, 3, 4}. The distance between any two of these cities is 2.

  2. 6

    {1,2,3,2,3}

    {2,3,4,5,6}

    {2,1,3,2,3}

    Returns: 3

    Again, the largest possible k is 3. There are two ways to select three equidistant cities: {1, 4, 6} and {4, 5, 6}. (In both cases the common distance is 6.)

  3. 10

    {1,1,1,1,1,1,1,1,1}

    {2,3,4,5,6,7,8,9,10}

    {1000,1000,1000,1000,1000,1000,1000,1000,1000}

    Returns: 9

  4. 2

    {1}

    {2}

    {3}

    Returns: 2

  5. 1

    {}

    {}

    {}

    Returns: 1

    Note that n can be 1.

  6. 5

    {1,1,4,2}

    {4,5,3,1}

    {423,422,422,424}

    Returns: 2

  7. 5

    {3,4,2,5}

    {1,2,3,4}

    {446,446,446,443}

    Returns: 2

  8. 9

    {1,6,3,9,6,1,6,6}

    {9,4,6,5,1,7,8,2}

    {827,823,825,827,827,823,824,826}

    Returns: 2

  9. 6

    {6,6,6,5,5}

    {2,5,1,3,4}

    {886,886,885,886,886}

    Returns: 3

  10. 3

    {3,3}

    {2,1}

    {91,91}

    Returns: 2

  11. 8

    {2,5,5,2,2,3,3}

    {5,6,3,8,4,7,1}

    {164,164,164,164,164,164,164}

    Returns: 3

  12. 9

    {2,1,7,9,2,6,9,7}

    {9,4,3,7,1,8,6,5}

    {345,345,345,346,346,345,344,346}

    Returns: 2

  13. 6

    {4,2,2,4,4}

    {3,5,6,2,1}

    {670,668,673,670,669}

    Returns: 2

  14. 9

    {2,7,7,3,9,7,6,3}

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

    {857,857,857,857,857,857,857,857}

    Returns: 3

  15. 9

    {3,1,3,3,3,9,7,7}

    {9,5,4,7,2,6,1,8}

    {490,489,490,490,490,488,489,490}

    Returns: 4

  16. 10

    {7,10,7,9,6,8,7,7,7}

    {5,2,10,4,8,1,6,3,9}

    {632,632,633,633,632,632,632,632,633}

    Returns: 3

  17. 5

    {2,2,1,5}

    {4,3,5,2}

    {108,108,109,107}

    Returns: 2

  18. 6

    {3,6,5,3,5}

    {6,2,1,5,4}

    {291,290,291,288,288}

    Returns: 2

  19. 8

    {6,5,5,7,8,3,1}

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

    {75,76,74,77,77,73,73}

    Returns: 2

  20. 6

    {3,3,6,6,2}

    {6,2,5,4,1}

    {585,586,584,584,586}

    Returns: 2

  21. 7

    {7,6,2,1,5,1}

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

    {250,253,251,250,251,251}

    Returns: 2

  22. 7

    {4,4,2,7,4,1}

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

    {278,280,279,278,283,279}

    Returns: 2

  23. 7

    {5,7,4,5,1,7}

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

    {683,682,682,682,682,683}

    Returns: 2

  24. 10

    {2,5,9,2,2,9,6,10,5}

    {3,4,7,10,6,1,9,8,2}

    {890,887,888,888,890,889,888,890,889}

    Returns: 2

  25. 8

    {8,6,6,3,6,7,3}

    {4,3,8,1,2,5,7}

    {392,390,394,392,394,390,390}

    Returns: 2

  26. 9

    {5,9,5,5,4,3,3,4}

    {7,6,9,8,1,4,5,2}

    {379,379,378,379,378,379,378,380}

    Returns: 2

  27. 8

    {3,2,4,4,3,3,4}

    {1,7,6,2,5,8,3}

    {540,542,542,541,542,539,542}

    Returns: 2

  28. 10

    {5,5,5,4,10,9,5,9,9}

    {4,3,2,6,1,5,10,7,8}

    {18,18,18,18,18,18,18,18,18}

    Returns: 5

  29. 8

    {4,6,8,3,4,4,6}

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

    {321,321,321,321,321,321,321}

    Returns: 4

  30. 6

    {1,6,1,1,1}

    {2,5,4,6,3}

    {733,736,736,734,733}

    Returns: 2

  31. 10

    {6,1,5,1,1,7,5,10,5}

    {3,4,6,5,9,10,8,2,7}

    {322,320,324,323,323,323,325,321,322}

    Returns: 2

  32. 3

    {3,3}

    {2,1}

    {349,348}

    Returns: 2

  33. 6

    {6,1,6,5,6}

    {3,6,5,4,2}

    {884,885,884,885,884}

    Returns: 3

  34. 3

    {2,3}

    {3,1}

    {328,324}

    Returns: 2

  35. 8

    {1,7,2,7,7,2,7}

    {4,3,5,8,1,7,6}

    {299,299,300,299,301,303,303}

    Returns: 2

  36. 10

    {2,6,6,4,7,2,4,6,1}

    {9,5,2,8,1,3,10,7,4}

    {738,741,740,740,738,738,738,741,736}

    Returns: 2

  37. 8

    {3,5,5,8,8,7,3}

    {4,7,8,6,1,3,2}

    {656,654,655,655,654,656,656}

    Returns: 3

  38. 8

    {8,1,4,6,7,4,8}

    {6,8,2,5,4,3,7}

    {350,348,348,346,348,348,347}

    Returns: 3

  39. 3

    {2,2}

    {1,3}

    {98,99}

    Returns: 2

  40. 5

    {1,2,5,5}

    {4,5,3,1}

    {672,672,674,672}

    Returns: 2

  41. 5

    {4,4,3,3}

    {2,5,4,1}

    {872,873,876,872}

    Returns: 2

  42. 5

    {3,3,1,4}

    {2,4,5,1}

    {552,550,551,552}

    Returns: 2

  43. 9

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

    {8,4,2,6,7,3,1,9}

    {145,145,146,145,145,143,143,144}

    Returns: 2

  44. 4

    {3,1,3}

    {4,3,2}

    {149,149,149}

    Returns: 3

  45. 5

    {3,4,3,3}

    {2,1,4,5}

    {555,555,555,555}

    Returns: 3

  46. 8

    {2,1,1,2,8,7,8}

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

    {813,813,813,813,813,813,813}

    Returns: 3

  47. 6

    {2,6,2,1,1}

    {3,4,5,6,2}

    {727,727,727,727,727}

    Returns: 3

  48. 7

    {2,1,5,7,7,2}

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

    {664,664,664,664,664,664}

    Returns: 3

  49. 6

    {5,4,2,6,2}

    {3,1,6,4,5}

    {863,863,863,863,863}

    Returns: 2

  50. 10

    {4,10,7,2,7,9,9,6,10}

    {5,2,1,6,9,4,3,8,7}

    {498,498,498,498,498,498,498,498,498}

    Returns: 3

  51. 5

    {5,5,4,5}

    {1,4,3,2}

    {741,741,741,741}

    Returns: 3

  52. 8

    {5,1,6,3,6,5,6}

    {1,8,5,4,2,7,3}

    {708,708,708,708,708,708,708}

    Returns: 3

  53. 4

    {2,2,4}

    {4,1,3}

    {899,899,899}

    Returns: 2

  54. 8

    {5,5,4,5,4,5,4}

    {3,2,1,7,6,8,5}

    {876,876,876,876,876,876,876}

    Returns: 5

  55. 3

    {2,2}

    {3,1}

    {669,669}

    Returns: 2

  56. 10

    {10,10,10,10,10,5,5,10,5}

    {1,8,2,7,5,9,3,6,4}

    {375,375,375,375,375,375,375,375,375}

    Returns: 6

  57. 3

    {3,3}

    {1,2}

    {430,430}

    Returns: 2

  58. 8

    {3,3,3,3,2,3,2}

    {6,1,4,7,8,2,5}

    {708,708,708,708,708,708,708}

    Returns: 5

  59. 9

    {5,5,4,5,5,5,5,5}

    {3,7,5,6,8,2,1,9}

    {735,735,735,735,735,735,735,735}

    Returns: 8

  60. 10

    {4,10,4,4,4,4,4,10,4}

    {9,1,7,2,5,8,6,4,3}

    {750,750,750,750,750,750,750,750,750}

    Returns: 8

  61. 5

    {4,4,2,4}

    {5,1,3,2}

    {246,246,246,246}

    Returns: 3

  62. 7

    {3,7,3,3,7,7}

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

    {688,688,688,688,688,688}

    Returns: 4

  63. 8

    {4,4,4,4,4,4,1}

    {8,6,2,5,3,1,7}

    {450,450,450,450,450,450,450}

    Returns: 6

  64. 6

    {5,5,1,5,1}

    {2,3,6,1,4}

    {597,597,597,597,597}

    Returns: 3

  65. 6

    {6,4,6,6,6}

    {1,6,2,3,5}

    {253,253,253,253,253}

    Returns: 5

  66. 9

    {7,7,5,7,5,8,8,8}

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

    {248,248,248,248,248,248,248,248}

    Returns: 4

  67. 10

    {1,1,4,1,4,1,4,1,4}

    {10,2,8,5,7,3,1,6,9}

    {135,135,135,135,135,134,135,134,135}

    Returns: 4

  68. 6

    {3,5,3,3,1}

    {1,2,4,5,6}

    {80,80,80,81,81}

    Returns: 2

  69. 7

    {5,2,5,5,4,2}

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

    {589,589,589,589,589,589}

    Returns: 3

  70. 5

    {3,3,3,4}

    {4,1,5,2}

    {793,794,793,794}

    Returns: 2

  71. 7

    {6,6,4,6,5,5}

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

    {727,727,727,727,726,726}

    Returns: 3

  72. 8

    {5,5,3,7,7,7,5}

    {8,1,7,2,4,6,3}

    {241,241,241,241,241,241,241}

    Returns: 4

  73. 9

    {6,7,2,7,7,6,2,7}

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

    {22,21,21,21,22,21,22,22}

    Returns: 2

  74. 7

    {7,7,7,4,4,7}

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

    {797,798,797,797,799,798}

    Returns: 2

  75. 8

    {2,4,1,1,4,4,1}

    {7,2,3,6,1,5,8}

    {316,315,316,315,315,316,316}

    Returns: 2

  76. 6

    {2,5,5,2,5}

    {6,4,1,3,2}

    {43,43,43,43,43}

    Returns: 3

  77. 7

    {5,1,1,6,6,5}

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

    {562,562,563,563,561,563}

    Returns: 2

  78. 4

    {4,1,4}

    {1,2,3}

    {349,350,349}

    Returns: 2

  79. 6

    {5,6,1,5,6}

    {4,2,6,1,3}

    {73,73,73,72,73}

    Returns: 3

  80. 10

    {5,1,5,9,9,1,9,9,5}

    {4,8,10,5,6,7,1,3,2}

    {669,669,670,669,669,669,670,669,670}

    Returns: 3

  81. 8

    {7,4,5,7,7,7,5}

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

    {12,12,11,12,12,13,13}

    Returns: 3

  82. 6

    {3,1,3,1,3}

    {5,2,1,4,6}

    {92,92,92,92,92}

    Returns: 3

  83. 9

    {7,2,7,7,7,2,6,6}

    {9,3,8,2,4,1,7,5}

    {61,62,61,62,62,61,62,62}

    Returns: 3

  84. 6

    {5,1,4,4,4}

    {2,3,5,6,1}

    {340,340,338,340,338}

    Returns: 2

  85. 10

    {6,5,5,5,5,5,10,5,6}

    {7,1,2,4,3,6,8,9,10}

    {149,149,149,149,149,149,149,149,149}

    Returns: 6

  86. 6

    {1, 2, 3, 2, 3 }

    {2, 3, 4, 5, 6 }

    {2, 1, 3, 2, 3 }

    Returns: 3

  87. 10

    {1, 1, 1, 1, 1, 1, 1, 1, 1 }

    {2, 3, 4, 5, 6, 7, 8, 9, 10 }

    {1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000 }

    Returns: 9

  88. 5

    {1, 1, 3, 3 }

    {2, 3, 4, 5 }

    {1, 1, 2, 2 }

    Returns: 3

  89. 10

    {1, 2, 3, 4, 5, 6, 7, 8, 9 }

    {2, 3, 4, 5, 6, 7, 8, 9, 10 }

    {1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000 }

    Returns: 2

  90. 1

    { }

    { }

    { }

    Returns: 1

  91. 5

    {1, 1, 1, 1 }

    {2, 3, 4, 5 }

    {1, 1, 1, 2 }

    Returns: 3

  92. 4

    {1, 3, 1 }

    {2, 4, 3 }

    {1, 1, 1 }

    Returns: 2

  93. 6

    {3, 1, 2, 2, 1 }

    {1, 2, 4, 5, 6 }

    {1, 1, 2, 2, 1 }

    Returns: 3

  94. 6

    {1, 1, 1, 4, 4 }

    {2, 3, 4, 6, 5 }

    {10, 10, 5, 5, 5 }

    Returns: 3

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.
This problem was used for: