Santa's Gift
Contest: Divide by Zero 2018 and Codeforces Round 474 (Div. 1 + Div. 2, combined)
Difficulty rating: 3100
Tags: data structures, trees

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$$$.

Input format:
The first line of the input contains four integers $$$n$$$ ($$$2 \leqslant n \leqslant 5 \cdot 10^4$$$), $$$m$$$, $$$q$$$, $$$C$$$ ($$$1 \leqslant m, q \leqslant 5 \cdot 10^4$$$, $$$0 \leqslant C \leqslant 10^6$$$) — the number of nodes, total number of different flavours of candies, the number of queries and the price charged by the Bakers for replacement, respectively.

The second line contains $$$n$$$ integers $$$f_1, f_2, \dots, f_n$$$ ($$$1 \leqslant f_i \leqslant m$$$), where $$$f_i$$$ is the initial flavour of the candy in the $$$i$$$-th node.

The third line contains $$$n - 1$$$ integers $$$p_2, p_3, \dots, p_n$$$ ($$$1 \leqslant p_i \leqslant n$$$), where $$$p_i$$$ is the parent of the $$$i$$$-th node.

The next line contains $$$m$$$ integers $$$c_1, c_2, \dots c_m$$$ ($$$1 \leqslant c_i \leqslant 10^2$$$), where $$$c_i$$$ is the cost of replacing one candy of flavour $$$i$$$.

The next $$$q$$$ lines describe the queries. Each line starts with an integer $$$t$$$ ($$$1 \leqslant t \leqslant 2$$$) — the type of the query.

If $$$t = 1$$$, then the line describes a query of the first type. Two integers $$$x$$$ and $$$w$$$ follow ($$$1 \leqslant  x \leqslant  n$$$, $$$1 \leqslant  w \leqslant m$$$), it means that Santa replaces the candy at vertex $$$x$$$ with flavour $$$w$$$.

Otherwise, if $$$t = 2$$$, the line describes a query of the second type and an integer $$$k$$$ ($$$1 \leqslant k \leqslant m$$$) follows, it means that you should print the expected value of the error in calculating the cost of replacement for a given flavour $$$k$$$.

The vertices are indexed from $$$1$$$ to $$$n$$$. Vertex $$$1$$$ is the root.

Output format:
Output the answer to each query of the second type in a separate line.

Your answer is considered correct if its absolute or relative error does not exceed $$$10^{-6}$$$.

Formally, let your answer be $$$a$$$, and the jury's answer be $$$b$$$. The checker program considers your answer correct if and only if $$$\frac{|a-b|}{max(1,b)}\leqslant 10^{-6}$$$.

Constraints:
Time limit: 4.0 s
Memory limit: 512.0 MB

Note:
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}$$$.

Example input:
3 5 5 7
3 1 4
1 1
73 1 48 85 89
2 1
2 3
1 2 3
2 1
2 3

Example output:
2920.333333333333
593.000000000000
49.000000000000
3217.000000000000

Editorial:
The actual cost of replacing all candies of flavour $$$k$$$ in the subtree of vertex $$$x$$$ is $$$h_k(x) \cdot c_k$$$. Here, $$$h_k(x)$$$ is the number of vertices (candy) in the subtree of $$$x$$$ with value (flavour) $$$k$$$ and $$$c_k$$$ is the cost of replacing each candy of flavour $$$k$$$.
Error $$$E(v)$$$ is defined as $$$(h_k(x) \cdot c_k – C) ^ 2$$$ = $$$h_k(x)^2 \cdot c_k^2 + C^2 – 2 \cdot h_k(x) \cdot c_k \cdot C$$$.
Expectation of error $$$E(v)$$$ can be written $$$Exp[E(v)]$$$ = $$$Exp[h_k(x)^2 \cdot c_k^2 + C^2 – 2 \cdot h_k(x) \cdot c_k \cdot C]$$$ = $$$c_k ^ 2 \cdot Exp[h_k(x)^2] + Exp[C^2] – 2 \cdot c_k \cdot C \cdot Exp[h_k(x)]$$$.
$$$Exp[h_k(x)]$$$ can be expressed as $$$\frac{\sum_{x=1}^{n} h_k(x)}{n}$$$. The above sum can be managed by adding or by subtracting the depth of node (assuming root to be of depth 1).       $$$Exp[{h_k(x)}^2]$$$ can be expressed as $$$\frac{\sum_{x=1}^{n} h_k(x)^2}{n}$$$. It can be observed that for every pair of vertices with value $$$k$$$ we need to add depth of LCA to the answer.
$$$$$$\sum_{x=1}^{n} h_k(x)^2 = \sum\nolimits_{f_i=k} \sum\nolimits_{f_j=k} Depth(LCA(i,j)) = \sum\nolimits_{f_i=k} \sum\nolimits_{f_j=k} Dist(i,j) / 2 – Depth(i) – Depth(j) $$$$$$
Now we need to find the summation $$$\sum\nolimits_{f_i=k} \sum\nolimits_{f_j=k} Dist(i,j)$$$.
To find sum we use centroid decomposition. We create a centroid tree from the given tree. Initially, no vertices have been inserted or updated. We update vertices one by one. While inserting a vertex with value $$$k$$$. We need to calculate its distance with all other vertices with the same value and add to the answer. To do so we maintain few things for a given vertex $$$x$$$ in the centroid tree.
• $$$p(x)$$$ — Parent of vertex $$$x$$$ in the centroid tree
• $$$h_k(x)$$$ — Number of vertices currently present in the subtree of $$$x$$$ with value $$$v$$$
• $$$a_k(x)$$$ — $$$\sum\nolimits_{i \in subtree(x)} distance(x,i)$$$
• $$$b_k(x)$$$ — $$$\sum\nolimits_{i \in subtree(x)} distance(p(x),i)$$$
The distance of any given vertex $$$x$$$ with value $$$k$$$ with other vertices of same value is given as $$$a_k(x) + d_k(x)$$$.
Here, $$$d_k(x)$$$ is $$$\sum\nolimits_{i \in all\ ancestor\ of\ x} distance(i,x) \cdot (h_k(p(i) - h_k(i)) + a_k(p(i)) - b_k(i))$$$
For each vertex, we need to store for all values $$$k$$$ present in the subtree. We can use a map for this purpose. In worst case, $$$O(n \cdot log(n))$$$ memory will be used.