题目描述

你决定设计你自己的软件包管理器。软件包之间有依赖关系：如果软件包 $A$ 依赖软件包 $B$，那么安装软件包 $A$ 以前，必须先安装软件包 $B$。同时，如果想要卸载软件包 $B$，则必须卸载软件包 $A$。

除 $0$ 号软件包以外，每个软件包都会依赖一个且仅一个软件包，而 $0$ 号软件包不依赖任何一个软件包。依赖关系不存在环，也不会有一个软件包依赖自己。

现在你要为软件包管理器写一个依赖解决程序。根据反馈，用户希望在安装和卸载某个软件包时，快速地知道这个操作实际上会改变多少个软件包的安装状态（即安装操作会安装多少个未安装的软件包，或卸载操作会卸载多少个已安装的软件包）。注意，安装一个已安装的软件包，或卸载一个未安装的软件包，都不会改变任何软件包的安装状态，即在此情况下，改变安装状态的软件包数为 $0$。

输入格式

输入的第 $1$ 行包含 $1$ 个正整数 $n$，表示软件包的总数。软件包从 $0$ 开始编号。

随后一行包含 $n-1$ 个整数，相邻整数之间用单个空格隔开，分别表示 $1,2,3,\dots ,n-2,n-1$ 号软件包依赖的软件包的编号。

接下来一行包含一个正整数 $q$，表示询问的总数。

之后 $q$ 行，每行一个询问。询问分为两种：

• install x：表示安装软件包 $x$
• uninstall x：表示卸载软件包 $x$

你需要维护每个软件包的安装状态，一开始所有的软件包都处于未安装状态。对于每个操作，你需要输出这步操作会改变多少个软件包的安装状态，随后应用这个操作（即改变你维护的安装状态）。

输出格式

输出包括 $q$ 行。 输出文件的第 $i$ 行输出一个整数，为第 $i$ 步操作中改变安装状态的软件包数。

样例

输入样例 1

7
0 0 0 1 1 5
5
install 5
install 6
uninstall 1
install 4
uninstall 0

输出样例 1

3
1
3
2
3

样例解释

依赖关系：
$0$ 号软件包无依赖。
$1,2,3$ 号软件包依赖 $0$。
$4,5$ 号软件包依赖 $1$。
$6$ 号软件包依赖 $5$。
树结构：

        0
      / | \
     1  2  3
    / \
   4   5
        \
         6

初始所有软件包未安装。

1. install 5：安装 $5$ 需要先安装 $0,1,5$（因为 $5$ 依赖 $1$，$1$ 依赖 $0$）。安装 $3$ 个软件包，输出 $3$。
2. install 6：安装 $6$ 需要先安装 $6$（因为 $5$ 已安装），输出 $1$。
3. uninstall 1：卸载 $1$ 需要卸载 $1,5,6$（因为 $5,6$ 依赖 $1$），输出 $3$。
4. install 4：安装 $4$ 需要先安装 $1,4$（因为 $4$ 依赖 $1$），输出 $2$。
5. uninstall 0：卸载 $0$ 需要卸载所有软件包（$0,1,4$），输出 $3$。

数据范围

• $n \le 10^5$
• $q \le 10^5$

时间限制：1000 ms
内存限制：262144 KB

提示

依赖关系形成一棵以 $0$ 为根的树。每个软件包依赖它的父节点。

• 安装操作 install x：需要安装 $x$ 以及 $x$ 到根节点路径上所有未安装的软件包。因此，改变的数量 = $x$ 到根节点路径上未安装的节点数。
• 卸载操作 uninstall x：需要卸载 $x$ 以及 $x$ 的子树中所有已安装的软件包。因此，改变的数量 = $x$ 的子树中已安装的节点数。

我们可以用树链剖分维护每个节点的安装状态（$0$ 表示未安装，$1$ 表示已安装）。线段树维护区间和（即已安装的节点数）。

对于 install x：

1. 查询 $x$ 到根节点路径上已安装的节点数 $cnt$。
2. 该路径上的节点总数为 $depth[x] + 1$（如果根深度为 $0$）。
3. 未安装的节点数 = 路径总节点数 $-$ 已安装节点数。
4. 输出该值，并将路径上所有节点标记为已安装（区间赋值为 $1$）。

对于 uninstall x：

1. 查询 $x$ 的子树中已安装的节点数 $cnt$。
2. 输出该值，并将子树中所有节点标记为未安装（区间赋值为 $0$）。

由于需要区间赋值和区间求和，线段树需要支持懒标记（覆盖标记）。

注意：树链剖分时，路径查询需要从 $x$ 向上跳到根，每次查询一条重链的区间和，并累加。
子树查询对应 DFS 序区间 $[in[x], out[x]]$。

时间复杂度：$O((n+q) \log^2 n)$，对于 $n,q \le 10^5$ 可以接受。