JOIN
Get Time

   Problem Statement  

 Problem Statement for AverageVarianceSubtree

Problem Statement

    In probability theory and statistics, variance is the expectation of the squared deviation of a random variable from its mean. As a special case, we can compute the variance of a nonempty finite collection of numbers X = { x_1, ..., x_n } as follows:
  1. Let mu = (x_1 + ... + x_n) / n be the mean of the collection.
  2. Let y_i = (x_i - mu)^2 be the square of the difference between x_i and the mean.
  3. The variance of X, denoted var(X), can now be computed as the average of all y_i. (In other words, as the sum of all y_i, divided by n.)
For example, if X = { 0, 1 }, we have mu = 1/2, then y_1 = y_2 = 1/4, and finally var(X) = (1/4 + 1/4) / 2 = 1/4.



Another example: suppose X = { 0, 0, 0, 1 }. Now we have mu = 1/4. Then we compute that y_1 = y_2 = y_3 = 1/16 and y_4 = 9/16. The average of these four values is 3/16.



You are given a tree T with n vertices, labeled 0 through n-1. More precisely, you are given the int[] p with n-1 elements that describes the edges of the tree. For each valid i, there is an edge between (i+1) and p[i]. The constraints ensure that this will always be a valid tree.



Each vertex of the tree has a positive integer weight. You are given these weights in the int[] weight with n elements.



A subtree of the tree T is any subgraph that is a tree. Alice found all nonempty subtrees of T. For each of them, she took the collection of weights of its vertices and she computed its variance. Bob then computed the average of all the variances computed by Alice. Compute and return the number Bob computed.
 

Definition

    
Class:AverageVarianceSubtree
Method:average
Parameters:int[], int[]
Returns:double
Method signature:double average(int[] p, int[] weight)
(be sure your method is public)
    
 

Notes

-The returned value must have an absolute or relative error less than 1e-9.
 

Constraints

-weight will contain between 1 and 50 elements, inclusive.
-Each element in weight will be between 1 and 1,000,000,000, inclusive.
-p will contain exactly |weight|-1 elements.
-For each i, 0 <= p[i] <= i.
 

Examples

0)
    
{0,1}
{10,20,30}
Returns: 19.444444444444443
The tree contains the edges 1-0 and 2-1. Thus, it looks as follows: 0-1-2. This tree has six different subtrees. These correspond to the following collections of weights: {10}, {20}, {30}, {10,20}, {20,30}, and {10,20,30}. Their variances are 0, 0, 0, 25, 25, and 200/3. The return value is the average of these six numbers.
1)
    
{0,1,1}
{10,20,7,6}
Returns: 23.0145202020202
This time the tree looks as shown below. (The numbers in the figure are the weights of those vertices.)
10 - 20 - 7
     |
     6
This tree has 11 nonempty subtrees. Below we list the collection of weights and its variance for each of the subtrees.
  • {10}, 0.0000000000000000
  • {20}, 0.0000000000000000
  • {7}, 0.0000000000000000
  • {6}, 0.0000000000000000
  • {10,20}, 25.0000000000000000
  • {7,20}, 42.2500000000000000
  • {6,20}, 49.0000000000000000
  • {20,7,6}, 40.6666666666666643
  • {10,20,6}, 34.6666666666666643
  • {10,20,7}, 30.8888888888888857
  • {10,20,7,6}, 30.6875000000000000
2)
    
{0}
{1,1000000000}
Returns: 8.3333333166666672E16
The answer can be very large
3)
    
{0,0,1,0,2,3,3,6}
{1,11,111,1111,11111,111111,1111111,11111111,111111111}
Returns: 4.432586365551198E14
4)
    
{}
{712}
Returns: 0.0

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 712 Round 1 - Division I, Level Two