Falsita(Disillusioning & Shinrein)

Falsita(Disillusioning & Shinrein)

测试数据来自 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 水题+原题赛

信息

ID
1912
难度
(无)
分类
(无)
标签
递交数
0
已通过
0
通过率
?
上传者