BearUniqueDiameter | Topcoder Archive

Problem Statement

A tree is a connected undirected graph without cycles. The distance between two vertices is the number of edges on the unique simple path that connects them. The diameter of a tree is the maximum distance between two of its vertices.

Bears hate ties and love uniqueness. They call a tree nice if there is exactly one unordered pair of vertices (x, y) such that the distance between x and y is equal to the diameter of the tree. (Note that x and y may be identical. In particular, this means that each tree with a single vertex is nice.)

Bear Limak has a tree with N vertices, numbered 0 through N-1. The tree is not necessarily nice. Limak wants to choose some non-empty subtree (i.e., a connected subgraph) of his tree and give it as a gift to someone. Of course, the chosen subtree must be nice.

You are given the description of Limak's tree: the int[]s a and b, each with N-1 elements. For each valid i, there is an edge between vertices a[i] and b[i]. Find and return the number of nice subtrees in Limak's tree, modulo 1,000,000,007.

Definition

Class:: BearUniqueDiameter
Method:: countSubtrees
Parameters:: int[], int[]
Returns:: int
Method signature:: int countSubtrees(int[] a, int[] b)
(be sure your method is public)

Notes

N will be between 2 and 300, inclusive.
a and b will each have exactly N elements.
Each element in a and in b will be between 0 and N-1, inclusive.
The given N-1 edges will form a tree.

Constraints

Examples

```
{0,0,0}
```
```
{1,2,3}
```
```
Returns: 10
```
The given tree has 4 vertices and 3 edges: 0-1, 0-2, 0-3. There are the following types of subtrees: The whole tree is also its own subtree. Its diameter is 2. Unfortunately, there is more than one pair of vertices with the distance 2 (the three pairs are: 1-2, 1-3, 2-3). Hence, this subtree is not nice and we don't count it towards the answer. There are 3 subtrees with 3 vertices each. Each of them is nice. There are 3 subtrees with 2 vertices each. Each of them is also nice. Finally, there are 4 subtrees with 1 vertex each. As we already explained above, each of these is nice as well. The answer is 3 + 3 + 4 = 10.
```
{3,2,1,4,0}
```
```
{1,3,4,0,5}
```
```
Returns: 21
```
```
{0,1,2,3,2}
```
```
{1,2,3,4,5}
```
```
Returns: 22
```
```
{1}
```
```
{0}
```
```
Returns: 3
```

{36,23,33,33,33,24,33,33,33,33,37,33,33,33,33,28,33,33,22,33,
29,16,33,33,33,33,33,31,35,33,33,8,13,26,12,33,33,0,33,33}

{33,33,0,9,39,33,32,40,15,19,33,30,38,7,25,33,27,11,33,3,33,33,
21,18,5,6,4,33,11,14,10,33,33,33,33,20,2,1,34,17}

Returns: 719477120

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

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

Returns: 70

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.