3683 - Falsita
描述 到海边了呢...... 如果没有那次选择,现在是不是会好些呢...... 都过去了。 仰望着星空,迎面吹过一阵阵海风,倚靠着护栏,Fine 在海边静静地伫立着,在一个个无际的长夜后,Fine 终于放下了往事的痛楚,得到了治愈。 但是作为 Fine 的另一重人格的 Falsita 就没那么幸运了。她仍然被各种繁忙的事务困扰着。 虽然同在一副躯体中,Fine 与 Falsita 的精神世界却相差甚远,Fine 可以轻易地构造出幻梦时,Falsita 却只能停留在现实的痛楚中。 但是为了生活需要,她们还是需要经常达成共识。 让我们形式化的描述一下吧。 她们所在的精神世界是一棵以 1 号节点为根的树,每个树上的节点 u 都有一个权值Wu,她们每个人分别都在一个节点上,达成共识的方法就是两个人都到达一个共识节点(即到达它们的最近公共祖先)。 一个点 u 与另外一个点 v 之间想要达到共识需要花费的代价为Wu+Wv。 有时两人的精神有所触动时,有时点的权值会改变成某个数,有时以某个点的子树中的所有点的权值会加上某个数。 Falsita 和 Fine 经常需要达成共识,每一次询问,已知达成的共识节点,求她们花费的期望代价。
Input
输入共 m + 3 行。 第一行两个整数 n, m ,表示节点个数和操作数。 第二行 n - 1 个整数Pi,表示节点 i ( i = 2 . . . n ) 的父亲节点的编号。 第三行 n 个整数Wi。 接下来 m 行,每行表示一个操作。
- S u delta 表示将节点 u 的权值加上 delta 。
- M u delta 表示将以节点 u 为根的子树中的所有节点的权值加上 delta。
- Q u 表示询问共识节点为 u 时的答案。 询问保证 u 不是叶子节点。
Output
对于每组询问,输出答案,答案精确到小数点后 6 位。 你的程序输出的答案需要与标准答案之差不超过10^(-5)。
Examples
Input
4 6 1 2 2 0 -6 3 0 S 2 -5 M 3 8 S 1 -1 M 4 7 M 3 2 Q 1
Output
2.000000
Hint
前5个操作后，四个节点的权值分别为-1,-11,13,7。最近公共祖先为1的点对有(1,2),(1,3),(1,4)，权值和分别为-12,12,6，故答案为(-12+12+6)/3=2。
对于 100% 的数据,1 ≤ n, m ≤ 300000, 0≤ |delta|, |Wi|≤ 20000。