软件包管理器

【题目描述】

你决定设计你自己的软件包管理器。不可避免的，你要解决软件包之间的依赖关系。如果A依赖B，那么安装A之前需安装B，卸载B之前须卸载A。0号软件包不依赖任何软件包。依赖关系不存在环(包括自环)。

你的任务是，求出每次安装、删除操作会改变多少个包的状态。

安装一个已安装的软件包，或者卸载一个未安装的软件包，都不会改变任何软件包的安装状态，即在此情况下，改变安装状态的软件包数为0

每次操作不仅需要计算安装软件包数，还作为操作影响后来的安装/删除

【输入格式】

第一行一个整数n,表示软件包的总数。

随后n-1个整数$a_1,a_2,...a_{n-1}$，表示第i个软件包依赖第$a_i$个软件包

接下来一行一个整数q,表示询问数

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

install x：表示安装x

uninstall x：表示卸载x

【输出格式】

q行，每行一个整数，为第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

【样例说明1】

一开始所有的软件包都处于未安装状态。

安装5号软件包，需安装0,1,5三个软件包

之后安装6号软件包，只需安装6号软件包。此时安装了0,1,5,6四个软件包。

卸载1号软件包需要卸载1,5,6三个软件包，此时只有0号软件包还处于安装状态

之后安装4号软件包，需安装1,4两个软件包。此时0,1,4处于安装状态

最后，卸载0号软件包会卸载所有的软件包

【样例输入2】

10
0 1 2 1 3 0 0 3 2
10
install 0
install 3
uninstall 2
install 7
install 5
install 9
uninstall 9
install 4
install 1
install 9

【样例输出2】

1
3
2
1
3
1
1
1
0
1

【数据范围】

1,2:n=5000 q=5000

3,4:n=100000 q=100000 没有卸载操作

5,6,7,8 n=100000,q=100000 依赖关系和操作随机

9-20 n=100000,q=100000 不随机

【来源】

NOI2015Day1T2