← 返回题目列表

Codeforces · 482/E

E. 增强型最近公共祖先

中文机器翻译题面 查看原题

你有一个包含 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。这种情况的一个示例是样本中的最后一个查询。