CF960H Santa's Gift

Santa has an infinite number of candies for each of $ m $ flavours. You are given a rooted tree with $ n $ vertices. The root of the tree is the vertex $ 1 $ . Each vertex contains exactly one candy. The $ i $ -th vertex has a candy of flavour $ f_i $ . Sometimes Santa fears that candies of flavour $ k $ have melted. He chooses any vertex $ x $ randomly and sends the subtree of $ x $ to the Bakers for a replacement. In a replacement, all the candies with flavour $ k $ are replaced with a new candy of the same flavour. The candies which are not of flavour $ k $ are left unchanged. After the replacement, the tree is restored. The actual cost of replacing one candy of flavour $ k $ is $ c_k $ (given for each $ k $ ). The Baker keeps the price fixed in order to make calculation simple. Every time when a subtree comes for a replacement, the Baker charges $ C $ , no matter which subtree it is and which flavour it is. Suppose that for a given flavour $ k $ the probability that Santa chooses a vertex for replacement is same for all the vertices. You need to find out the expected value of error in calculating the cost of replacement of flavour $ k $ . The error in calculating the cost is defined as follows. $$ Error\ E(k) =\ (Actual Cost\ –\ Price\ charged\ by\ the\ Bakers) ^ 2. $$ Note that the actual cost is the cost of replacement of one candy of the flavour $ k $ multiplied by the number of candies in the subtree. Also, sometimes Santa may wish to replace a candy at vertex $ x $ with a candy of some flavour from his pocket. You need to handle two types of operations: - Change the flavour of the candy at vertex $ x $ to $ w $ . - Calculate the expected value of error in calculating the cost of replacement for a given flavour $ k$.

N/A

N/A

For $ 1 $ -st query, the error in calculating the cost of replacement for flavour $ 1 $ if vertex $ 1 $ , $ 2 $ or $ 3 $ is chosen are $ 66^2 $ , $ 66^2 $ and $ (-7)^2 $ respectively. Since the probability of choosing any vertex is same, therefore the expected value of error is $ \frac{66^2+66^2+(-7)^2}{3} $ . Similarly, for $ 2 $ -nd query the expected value of error is $ \frac{41^2+(-7)^2+(-7)^2}{3} $ . After $ 3 $ -rd query, the flavour at vertex $ 2 $ changes from $ 1 $ to $ 3 $ . For $ 4 $ -th query, the expected value of error is $ \frac{(-7)^2+(-7)^2+(-7)^2}{3} $ . Similarly, for $ 5 $ -th query, the expected value of error is $ \frac{89^2+41^2+(-7)^2}{3} $ .