DiameterOfRandomTree | Topcoder Archive

Problem Statement

Given a tree, let d(u,v) be the distance between nodes u and v in the tree. In other words, d(u,v) is the length of the only simple path that connects u and v. The diameter of the tree is the maximum of all d(u,v).

You are given int[]s a and b, each containing n-1 elements. These describe a tree with n nodes, labeled 0 through n-1. For each valid i, the nodes a[i] and b[i] are connected by an edge.

The length of each edge is generated randomly. More precisely, the length of each edge is either 1 or 2 with equal probability. The lengths of edges are mutually independent.

Return the expected value of the diameter of the given tree.

Definition

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

Constraints

a will contain between 1 and 50 elements, inclusive.
a and b will contain the same number of elements.
Each element in a will be between 0 and |a|, inclusive.
Each element in b will be between 0 and |a|, inclusive.
The graph will be a tree.

Examples

```
{0,1,2,3}
```
```
{1,2,3,4}
```
```
Returns: 6.0
```
This graph is a single path: 0-1-2-3-4. In this case, the diameter will always be the distance between nodes 0 and 4. The expected length of each edge is 1.5, thus the expected distance between 0 and 4 equals 4 * 1.5 = 6.
```
{0,0,0}
```
```
{1,2,3}
```
```
Returns: 3.375
```
This tree has three edges: 0-1, 0-2, and 0-3. There are four possible cases: With probability 1/8 all three edges have length 1. In this case, the diameter is 2. With probability 3/8 the edges have lengths (1,1,2). In this case, the diameter is 3. With probability 3/8 the edges have lengths (1,2,2). In this case, the diameter is 4. With probability 1/8 all three edges have length 2. In this case, the diameter is also 4. Thus, the expected diameter is (1/8)*2 + (3/8)*3 + (3/8)*4 + (1/8)*4 = 27/8 = 3.375.
```
{0,0,0,1,4}
```
```
{1,2,3,4,5}
```
```
Returns: 6.25
```

{0,0,0,0,0,0,0,0}

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

Returns: 3.9609375

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

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

Returns: 10.53125

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.