测试数据来自 system/1887

背景

为了一个梦想
也必须有所放弃
即使现在就是指爱
我依旧迷惑该何去何从
——旋律

描述

到海边了呢……
如果没有那次选择，现在是不是会好些呢……
都过去了。
仰望着星空，迎面吹过一阵阵海风，倚靠着护栏，Fine 在海边静静地伫立着，在一个个无际的长夜后，Fine 终于放下了往事的痛楚，得到了治愈。
但是作为Fine 的另一重人格的Falsita 就没那么幸运了。她仍然被各种繁忙的事务困扰着。
虽然同在一副躯体中，Fine 与Falsita 的精神世界却相差甚远，Fine 可以轻易地构造出幻梦时，Falsita 却只能停留在现实的痛楚中。
但是为了生活需要，她们还是需要经常达成共识。
让我们形式化的描述一下吧。
她们所在的精神世界是一棵以1 号节点为根的树，每个树上的节点u 都有一个权值Wu，她们每个人都在一个节点上，但不会在同一个节点上，达成共识的方法就是两个人都到达一个共识节点（即到达它们的最近公共祖先）。
一个点u 与另外一个点v 之间想要达到共识需要花费的代价为Wu +Wv 。
有时两人的精神有所触动时，有时点的权值会改变成某个数，有时以某个点的子树中的所有点的权值会加上某个数。
Falsita 和Fine 经常需要达成共识，每一次询问，已知达成的共识节点，求她们花费的期望代价。

格式

输入格式

输入共m + 3 行。
第一行两个整数n;m ，表示节点个数和操作个数。
第二行n - 1 个整数Pi ，表示节点i ( i = 2...n ) 的父亲节点的编号。
第三行n 个整数Wi 。
接下来m 行，每行表示一个操作。
1. S u delta 表示将节点u 的权值加上delta 。
2. M u delta 表示将以节点u 为根的子树中的所有节点的权值加上delta。
3. Q u 表示询问共识节点为u 时的答案。

输出格式

对于每组询问，输出答案，答案精确到 小数点后3位 。
由于没有Special Judge…………
所以你必须保证你的答案与标准答案一样。

样例1

样例输入1

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

样例输出1

2.000

限制

对于10% 的数据，1 <= n, m <= 2000 。
对于50% 的数据，1 <= n, m <= 80000 。
对于100% 的数据，1 <= n, m <= 300000
1 <= |delta|, |Wi| <= 20000 。
时限每点 2s 。

提示

前5个操作后，四个节点的权值分别为-1,-11,13,7。最近公共祖先为1的点对有(1,2),(1,3),(1,4)，权值和分别为-12,12,6，故答案为(-12+12+6)/3=2。

来源

Disillusioning #1 水题+原题赛