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:
 Let mu = (x_1 + ... + x_n) / n be the mean of the collection.
 Let y_i = (x_i  mu)^2 be the square of the difference between x_i and the mean.
 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 n1.
More precisely, you are given the int[] p with n1 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 1e9.   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 weight1 elements.    For each i, 0 <= p[i] <= i.   Examples  0)     Returns: 19.444444444444443  The tree contains the edges 10 and 21.
Thus, it looks as follows: 012.
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)     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)     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)    
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.
