#PT0213. 软件包管理器 (Package Manager)

软件包管理器 (Package Manager)

Description

Linux users and OSX users must be familiar with package managers. Through the package manager, you can install a certain software package with one line of command, and then the package manager will help you download the software package from the software source, and automatically resolve all dependencies (that is, download and install other software packages that this software package depends on), complete all configurations. apt-get is used by Debian/Ubuntu, yum is used by Fedora/CentOS, and Homebrew is available for OSX.

You decide to design your own package manager. Obviously, you have to solve the dependency problem between packages. If the software package AA depends on the software package BB, you must install the software package BB before installing the software package AA. At the same time, if you want to uninstall the software package BB, you must uninstall the software package AA. Now you have obtained all the dependencies between the packages. Moreover, due to your previous work, in addition to package 00, the packages in your manager will depend on one and only one package, and package 00 does not depend on any package. There is no ring of dependencies (if there are mm (m2m \geq 2) packages A1,A2,A3AmA_1,A_2,A_3\ldots A_m, where A1A_1 depends on A2A_2, A2A_2 depends on A3A_3, A3A_3 depends on A4A_4, \ldots, Am1A_{m - 1} depends on AmA_m and AmA_m depends on A1A_1, then it is said these mm packages form a ring) and no package depends on itself.

Now you have to write a dependency resolution program for your package manager. According to the user's actions, when installing and uninstalling a certain software package, users want to quickly know how many software packages' installation status will actually be changed by this operation (that is, how many uninstalled software packages will be installed by the installation operation, or the uninstall operation will uninstall how many installed packages), your task is to achieve this part. Note that installing an installed software package or uninstalling an uninstalled software package will not change the installation status of any software package, that is, in this case, the number of packages that have changed the installation status is 00.

Input Format

The 11 st line of the input file contains 11 positive integers nn, representing the total number of packages. The software packages are numbered starting from 00.

The following line contains n1n−1 integers, separated by a single space between adjacent integers, representing 1,2,3,,n2,n11, 2, 3, \ldots, n−2, n−1 software, the number of the software package that this software package depends on.

The next line contains a positive integer qq, which represents the total number of queries. Then qq lines follow, one query per line. There are two types of queries:

install x: indicates the installation package xx

uninstall x: means to uninstall the software package xx

You need to maintain the installation status of each package. At the beginning, all packages are in an uninstalled state. For each operation, you need to output how many software packages' installation state will change, and then apply this operation (that is, change the installation states you maintain).

Output Format

Output qq lines. Line ii of the output file outputs an integer, which is the number of packages whose installation status was changed in step ii.

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

Constraints

For all data, n100000, q100000n \leq 100000, \ q \leq 100000.