CF482E ELCA

有一棵以 $1$ 为根的有根树，第 $i$ 个节点的父亲为 $f_i$，每个节点上有一个数为 $a_i$。 共有 $m$ 个事件： - `P x y`: 若 $x$ 是 $y$ 的祖先，把 $f_y$ 改为 $x$，否则把 $f_x$ 改为 $y$。 - `V x v`: 把 $a_x$ 改为 $v$。 求初始和每个事件发生后随机两个点（可以是同一个点）的 LCA 的 $a_i$ 的期望。

第一行有一个整数 $n$，表示树的节点数量。 第二行有 $n-1$ 个整数，第 $i$ 个整数是 $f_{i+1}$， 表示节点 $i+1$ 的父节点。 第三行有 $n$ 个整数，第 $i$ 个整数是 $a_i$，表示节点 $i$ 的权值。 第四行有一个整数 $m$，接下来 $m$ 行每行有一个事件，格式如题目描述中所示。

共 $m+1$ 行，输出初始和每个事件发生后随机两个点（可以是同一个点）的 LCA 的 $a_i$ 的期望。如果你的答案绝对误差或相对误差不超过 $10^{-9}$，则将被视为正确。

保证： - 树的节点数量 $2\le n\le5\cdot10^4$。 - 询问次数 $1\le m\le5\cdot10^4$。 - 点权 $0\le a_i\le10^6$。 - 设第二种操作将点权改为 $v$，则所有 $v$ 满足 $0\le v\le10^6$。 - $i$ 的父节点 $1\le f_i\le n$。