题目描述

物理学家小 C 的研究正遇到某个瓶颈。

他正在研究的是一个星系，这个星系中有 $n$ 个星球，其中有一个主星球（方便起见我们默认其为 $1$ 号星球），其余的所有星球均有且仅有一个依赖星球。主星球没有依赖星球。

我们定义依赖关系如下：若星球 $a$ 的依赖星球是 $b$，则有星球 $a$ 依赖星球 $b$。此外，依赖关系具有传递性，即若星球 $a$ 依赖星球 $b$，星球 $b$ 依赖星球 $c$，则有星球 $a$ 依赖星球 $c$。

对于这个神秘的星系中，小 C 初步探究了它的性质，发现星球之间的依赖关系是无环的。并且从星球 $a$ 出发只能直接到达它的依赖星球 $b$。

每个星球 $i$ 都有一个能量系数 $w_i$。小 C 想进行若干次实验，第 $i$ 次实验，他将从飞船上向星球 $d_i$ 发射一个初始能量为 $0$ 的能量收集器，能量收集器会从星球 $d_i$ 开始前往主星球，并收集沿途每个星球的部分能量，收集能量的多少等于这个星球的能量系数。

但是星系的构成并不是一成不变的，某些时刻，星系可能由于某些复杂的原因发生变化。

有些时刻，某个星球能量激发，将使得所有依赖于它的星球以及他自己的能量系数均增加一个定值。还有可能在某些时刻，某个星球的依赖星球会发生变化，但变化后依然满足依赖关系是无环的。

现在小 C 已经测定了时刻 $0$ 时每个星球的能量系数，以及每个星球（除了主星球之外）的依赖星球。接下来的 $m$ 个时刻，每个时刻都会发生一些事件。其中小 C 可能会进行若干次实验，对于他的每一次实验，请你告诉他这一次实验能量收集器的最终能量是多少。

输入格式

第一行一个整数 $n$，表示星系的星球数。

接下来 $n-1$ 行每行一个整数，分别表示星球 $2 \sim n$ 的依赖星球编号。

接下来一行 $n$ 个整数，表示每个星球在时刻 $0$ 时的初始能量系数 $w_i$。

接下来一行一个整数 $m$，表示事件的总数。

事件分为以下三种类型。

• Q d 表示小 C 要开始一次实验，收集器的初始位置在星球 $d$。
• C x y 表示星球 $x$ 的依赖星球变为了星球 $y$。
• F p q 表示星球 $p$ 能量激发，常数为 $q$。

输出格式

对于每一个事件类型为 Q 的事件，输出一行一个整数，表示此次实验的收集器最终能量。

3
1
1
4 5 7
5
Q 2
F 1 3
Q 2
C 2 3
Q 2

9
15
25

数据规模与约定

对于 $100\%$ 的数据，$n \le 10^5$，$m \le 3 \times 10^5$，$1<d_i,x_i \le n$，$w_i,q_i \le 10^5$，保证操作合法。

题目来源

By 佚名上传