← 返回题目列表

Codeforces · 877/E

E. 丹尼尔和一份兼职工作

中文机器翻译题面 查看原题

丹尼尔决定赚点钱,所以他找到了一份兼职工作。面试很顺利,所以现在他是一名灯光开关师。

Danil 在一个有 n 个顶点的有根树(无向连通无环图)中工作,顶点 1 是树的根。每个顶点都有一个房间,每个房间的灯都可以打开或关闭。 Danil 的职责包括切换顶点子树所有房间的灯光。这意味着如果子树的某个房间的灯打开了,他应该将其关闭。否则,他应该打开它。

不幸的是(或者幸运的是),丹尼尔非常懒。他知道他的老板不会亲自检查工作。相反,他将使用 Workforces 个人消息向 Danil 发送任务。

有两种类型的任务:

1. pow v 描述了一个在顶点 v 的子树中开关灯的任务。
2. get v 描述了一个计算 v 子树中灯打开的房间数量的任务。丹尼尔应该使用劳动力消息将答案发送给他的老板。

顶点v的子树是从它们到根的最短路径经过v的顶点的集合。特别地,顶点v位于v的子树中。

丹尼尔不会履行他的职责。他要求你写一个程序,由它代替他回答老板。

输入

第一行包含一个整数 n (1 ≤ n ≤ 200 000) — 树中的顶点数。

第二行包含 n - 1 个空格分隔的整数 p2, p3, ..., pn (1 ≤ pi < i),其中 pi 是顶点 i 的祖先。

第三行包含 n 个空格分隔的整数 t1, t2, ..., tn (0 ≤ ti ≤ 1),其中如果灯在顶点 i 打开,则 ti 为 1,否则为 0。

第四行包含一个整数 q (1 ≤ q ≤ 200 000) — 任务数。

接下来的 q 行是 get v 或 pow v (1 ≤ v ≤ n) — 上面描述的任务。

输出

对于每个任务 get v 打印 v 子树中灯打开的房间数。

示例

输入 #1

4
1 1 1
1 0 0 1
9
get 1
get 2
get 3
get 4
pow 1
get 1
get 2
get 3
get 4

输出 #1

2
0
0
1
2
1
1
0

注意

任务 pow 1 之前的树。任务 pow 1 之后的树。