你有一个包含 n 个顶点的根树。让我们用 1 到 n 的整数对树顶点进行编号。树根位于顶点 1。
每个顶点(树根除外)v都有一个直接祖先pv。此外,每个顶点 v 都有其整数值 sv。
您的任务是执行以下查询:
- P v u (u ≠ v)。如果 u 不在 v 的子树中,则必须执行赋值 pv = u。否则,您必须执行赋值 pu = v。请注意,在此查询之后,图仍然是由 n 个顶点组成的树。
- V v t。执行赋值 sv = t。
您的任务如下。在开始执行查询之前和每次查询之后,您必须计算写在两个等概率选择的顶点 i 和 j 的最低公共祖先上的期望值。这里i和j的最低公共祖先是位于从根到顶点i的路径和从根到顶点j的路径上的最深顶点。请注意,顶点 i 和 j 可以相同(在这种情况下,它们的最低公共祖先与它们重合)。
输入
输入的第一行包含整数 n (2 ≤ n ≤ 5·104) — 树顶点的数量。
第二行包含 n - 1 个整数 p2, p3, ..., pn (1 ≤ pi ≤ n) — 树边的描述。保证这些数字形成一棵树。
第三行包含 n 个整数 — s1, s2, ... sn (0 ≤ si ≤ 106) — 写入树每个顶点的值。
下一行包含整数 q (1 ≤ q ≤ 5·104) — 查询数。以下 q 行中的每一行都以语句中描述的格式包含查询的描述。保证查询参数 u 和 v 位于 1 和 n 之间。保证类型 V 的查询中的参数 t 满足限制 0 ≤ t ≤ 106。
输出
打印 q + 1 数字 — 相应的期望值。如果您的答案的绝对或相对误差不超过 10 - 9,则视为正确。
示例
输入 #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
1.640000000 1.800000000 2.280000000 2.320000000 2.800000000 1.840000000
注意
请注意,在查询 P v u 中,如果 u 位于 v 的子树中,则必须执行赋值 pu = v。这种情况的一个示例是样本中的最后一个查询。