UOJ Logo Zijian Online Judge

ZOJ

#11. 政府

Statistics

政府总是一个庞大的系统,有着上下级关系,而且通常来说这种上下级关系构成一棵树。

一个政府中成员千千万万,虽说大部分官员为政清廉,但总不免会有那么一些苍蝇老虎为非作歹,也不免出现清官出于对某些问题的顾虑不严格按照规矩办事。

以上所述问题直接影响的就是基层民众的问题能否得到有效解决,所以天下百姓以人民的名义请你写一个系统,用来查询当我们向某个部门提交议案时得到解决程度的期望。

我们可以这样来看这个问题:

1、已知这个政府系统有 $n$ 个职能部门

2、我们认为每个部门都有一个编号,中央为编号 $1$ ,其他各部门编号为 $2$ 至 $n$。

3、每个非中央(编号大于1)部门都由一个上级领导部门领导,编号为 $lead_i$,这个上级关系图不会出现环(即必定构成一棵树),且所有部门一定最终归至中央领导(即中央为树根)。

4、这样每个部门会得到一个与其到中央距离(即节点深度)相等的行政等级 $lv_i$。

5、每份被提交到部门 $i$ 的议案拥有一个难度等级 $p$,$p = lv_i$

6、每个部门 $i$ 有一个上传概率 $A_i$,表示出于腐败或其他原因,一份议案到达部门 $i$ 后有 $A_i$ 的几率被上传至该部门的上级:部门$lead_i$。特别的,议案到了中央不会被继续上传(谁敢说自己是中央的领导)

7、当一份难度等级为 $p$ 议案被送到(可以通过提交上传两种方式到达)部门 $i$ 时,可以获得值为 $p - lv_i$ 解决程度

根据上述 $7$ 条规则,你每得到一个询问Query x,需要输出当一份议案被提交至部门 $x$ 时,得到的解决程度的期望是多少。

政坛风云变幻,世人难料,所以你经常会收到一些通知

通知内容分为两种:

1、Change x v,表示部门 $x$ 整改,其上传概率 $A_x$ 变成 $v$

2、Transfer x y,表示部门 $x$ 被重新编制到部门 $y$ 领导下,即 $lead_x = y$。注意,部门 $x$ 及其直接领导或间接领导的部门的行政等级都可能会发生改变

在收到通知后,你需要立即对你的系统进行维护,以使以后的查询能够更加准确

加油,人民看好你呦!

输入格式

第 $1$ 行包含一个正整数 $n$,表示政府部门数

第 $2$ 行包含 $n-1$ 个正整数 $lead_i$,依次表示编号由 $2$ 至 $n$ 的部门的上级领导部门的编号

第 $3$ 行包含 $n-1$ 个浮点数 $A_i$,依次表示编号由 $2$ 至 $n$ 的部门的上传概率

第 $4$ 行包含一个正整数 $m$,表示询问及通知总数

接下来 $m$ 行,每行包含一条指令,可能为以下三种的一种:Query xChange x vTransfer x y,具体意义见题面

输出格式

对于每个查询操作,输出查询结果,结果与参考答案的绝对误差与相对误差的较小值小于$0.0001$即可

样例一

input

5
3 1 1 3
0.2 0.5 0.0 0.3
13
Query 5
Change 3 0.8
Query 5
Query 3
Transfer 3 4
Change 4 0.7
Query 3
Query 2
Transfer 2 1
Query 2
Query 5
Transfer 4 2
Query 5

output

0.600000
0.780000
0.800000
1.920000
0.856000
0.200000
1.284000
1.418400

限制与约定

测试点编号$n, m$约束操作
1$n = 1000, m = 1000$//
2$n = 100000, m = 100000$只有Query操作
3
4初始$lead_i=i-1$Transfer操作
5
6/
7初始$A_i=1.0$Change操作
8
9//
10

时间限制:$1\texttt{s}$

空间限制:$256\texttt{MB}$