elca

ELCA

You have a rooted tree containing $n$ vertexes. Let's index these tree vertexes with integers from $1$ to $n$. The tree root is vertex $1$.

Each vertex (except for the tree root) $v$ has a direct ancestor $p_v$. Also, each vertex $v$ has an integer value $s_v$.

Your are to perform the following queries:

• P $v$ $u$ $(u\hspace{0.17em}\ne \hspace{0.17em}v)$. If $u$ isn't in the subtree of $v$, you must perform the assignment $p_v\hspace{0.17em}=\hspace{0.17em}u$. Otherwise you must perform the assignment $p_u\hspace{0.17em}=\hspace{0.17em}v$. Note that after this query the graph continues to be a tree consisting of $n$ vertexes.
• V $v$ $t$. Perform the assignment $s_v\hspace{0.17em}=\hspace{0.17em}t$.

The effects of each query carry over to subsequent queries.

Your task is as follows. Before the first query, and after each query, you have to calculate the expected value written on the lowest common ancestor of two equiprobably selected vertices $i$ and $j$. Here, the lowest common ancestor of $i$ and $j$ is the deepest vertex that lies on both the path from the root to vertex $i$ and the path from the root to vertex $j$. Please note that the vertices $i$ and $j$ can be the same (in this case their lowest common ancestor coincides with them). When $i$ and $j$ are different, the pair $(i,j)$ is considered distinct from $(j,i)$.

Input format

The first line of the input contains an integer $n$ $(2\hspace{0.17em}\le \hspace{0.17em}n\hspace{0.17em}\le 50000)$ — the number of tree vertexes.

The second line contains $n\hspace{0.17em}-\hspace{0.17em}1$ integers $p_2,\hspace{0.17em}{p}_3,\hspace{0.17em}...,\hspace{0.17em}{p}_n$ $(1\hspace{0.17em}\le \hspace{0.17em}{p}_i\hspace{0.17em}\le \hspace{0.17em}n)$ — the direct ancestor of every vertex. It is guaranteed that these edges form a tree.

The third line contains $n$ integers — $s_1,\hspace{0.17em}{s}_2,\hspace{0.17em}...s_n$ $(0\hspace{0.17em}\le \hspace{0.17em}{s}_i\hspace{0.17em}\le \hspace{0.17em}{10}^6)$ — the values written on each vertex of the tree.

The next line contains an integer $q$ $(1\hspace{0.17em}\le \hspace{0.17em}q\hspace{0.17em}\le \hspace{0.17em}50000)$ — the number of queries. Each of the following $q$ lines contains the description of a query in the format described in the statement. It is guaranteed that query arguments $u$ and $v$ lie between $1$ and $n$. It is guaranteed that argument $t$ in the queries of type $V$ meets limits $0\hspace{0.17em}\le \hspace{0.17em}t\hspace{0.17em}\le \hspace{0.17em}{10}^6$.

Output format

Print $q\hspace{0.17em}+\hspace{0.17em}1$ lines each containing a real number — the corresponding expected values. Your answer will be considered correct if its absolute or relative error doesn't exceed ${10}^{-6}$.

Limits

Subtask #	Score	Constraints
1	11	$n,q\le 200$
2	23	$n,q\le 2000$
3	22	All queries will be of type V.
4	24	$n,q\le 25000$
5	20	No additional constraints

Samples

Sample Input 1	Sample Output 1
5 1 2 2 1 1 2 3 4 5 5 P 3 4 P 4 5 V 2 3 P 5 2 P 1 4	1.640000000 1.800000000 2.280000000 2.320000000 2.800000000 1.840000000

Note that in the query P $v$ $u$, if $u$ lies in subtree of $v$ you must perform the assignment $p_u\hspace{0.17em}=\hspace{0.17em}v$. An example of such a case is the last query in the sample.