P14965 [LBA-OI R2 D] 昔涟

 δ-me13 (Cyrene)，and PhiLia093 (Cyrene) PhiLia093 在给 δ-me13 讲故事，在充满爱的故事中，带着她认识世界。为了检验 δ-me13 的学习成果，PhiLia093 设计了一个小问题。

δ-me13 眼中，桃子是充满美好的事物。 PhiLia093 给了 δ-me13 一棵有 $n$ 个节点的树。每个节点初始时没有或有一个桃子。有桃子的节点是粉色（用 `P` 表示），没有桃子的节点是白色（用 `W` 表示）。每个节点还有一个权值 $a_i$ ，初始 $a$ 全为 $0$ 。进行 $q$ 次操作，操作有以下三种。 1. 给出点 $u$ 。若 $u$ 是 `W`，则把 $u$ 变成 `P`，即放一个桃子；若 $u$ 是 `P`，则把 $u$ 变成 `W`，即拿走一个桃子。 2. 给出点 $u$ 和 $x$。对于所有的点 $v$（$u$ 可能等于 $v$），若 $u$ 到 $v$ 的最短路径上（包括 $u$ 和 $v$），有且仅有一个 `P`，则 $a_v\gets a_v+x$。 δ-me13 想要吃桃子，但她只能吃下一个。 3. 给出点 $u$ ，询问 $a_u$ 。 但是 δ-me13 已经回到翁法罗斯的过去了，在离开前也没解出答案，所以她将这个问题托付给你。 她会停留在扉页，等待你续写新的起点。 题外话：要不是空间开不下，我想弄一个 $n=33550337$ 的点。

第一行三个整数 $n,q$，表示树的结点个数、操作次数。 第二行一个长度为 $n$ 的、由字符 `W` 和 `P` 组成的字符串，表示每个节点初始时有没有桃子。 接下来一行 $n-1$ 个整数，第 $i$ 个为 $fa_{i+1}$。其中，$fa_u$ 表示 $u$ 的父亲节点编号。 接下来 $q$ 行，每行描述一个操作。形如以下三种： - `1 u` - `2 u x` - `3 u`

对于每个操作三，输出一行一个整数，表示答案。

| 子任务编号 | $n ,q \le$ | 特殊性质 |分值|时间限制| | :-----------: | :-----------: | :-----------: | :-----------: | :------------:| | $1$ | $3000$ | 无 | $5$ | $0.8s$ | | $2$ | $10^6$ | A | $10$ | $2s$ | | $3$ | $10^5$ | B | $25$ | $0.8s$ | | $4$ | $10^6$ | C | $20$ | $2s$ | | $5$ | $10^5$ | 无 | $15$ | $0.8s$ | | $6$ | $10^6$ | 无 | $25$ | $2s$ | 特殊性质 A：没有操作 1。 特殊性质 B：对于操作 1，保证 $u$ 在操作前颜色都是 `W`。 特殊性质 C：对于操作 1，保证 $u$ 在操作前颜色都是 `P`。 对于所有数据，满足 $1\le n,q\le 10^6$ , $1\le x\le 10^3$ 。 保证时间与空间限制均为 std 的 2 倍以上。