Software Package Manager

Problem Source

NOI 2015

Problem Description

Linux users and OS X users are certainly familiar with package managers. With a package manager you can install a software package with a single command, and the manager then downloads it from the source and automatically resolves all dependencies (downloading and installing whatever other packages that package depends on), finishing all configuration. apt-get on Debian/Ubuntu, yum on Fedora/CentOS, and homebrew on OS X are all excellent package managers.

You decide to design your own package manager. Inevitably, you must solve the dependency problem among packages. If package $A$ depends on package $B$, then before installing $A$ you must first install $B$. Likewise, to uninstall $B$ you must first uninstall $A$. You have already obtained all dependency relations between packages. Moreover, thanks to your previous work, every package other than package $0$ depends on exactly one other package, while package $0$ depends on none. There are no dependency cycles (a cycle would mean $A_1$ depends on $A_2$, $A_2$ on $A_3$, ..., $A_{m-1}$ on $A_m$, and $A_m$ on $A_1$, for some $m \ge 2$), and of course no package depends on itself.

Now you must write the dependency resolver for your package manager. Based on user feedback, when installing or uninstalling a package users want to know quickly how many packages' installation states this operation actually changes (i.e. how many uninstalled packages an install operation installs, or how many installed packages an uninstall operation removes). Your task is to implement this part. Note that installing an already-installed package, or uninstalling an already-uninstalled package, changes no package's installation state — in those cases the number of changed packages is $0$.

Input Format

The first line of the input file contains one positive integer $n$, the total number of packages. Packages are numbered starting from $0$.

The following line contains $n - 1$ integers separated by single spaces, indicating the package that packages $1, 2, 3, \dots, n-1$ depend on, respectively.

The next line contains one positive integer $q$, the number of queries.

Then follow $q$ lines, each describing one query. There are two kinds of queries:

1. install x: install package $x$.
2. uninstall x: uninstall package $x$.

You must maintain the installation state of every package; initially all packages are uninstalled. For each operation, output how many packages' installation state this step changes, and then apply the operation (i.e. update the installation states you maintain).

It is guaranteed that $1 \leq n, q \leq 10^5$.

Output Format

The output file contains $q$ lines. The $i$-th line outputs one integer: the number of packages whose installation state changed in the $i$-th operation.

Sample Input

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

Sample Output

3
1
3
2
3

Sample Explanation

Initially all packages are uninstalled.

Installing package $5$ requires installing packages $0, 1, 5$ — three packages.

Then installing package $6$ only requires installing package $6$ itself. At this point $0, 1, 5, 6$ are installed.

Uninstalling package $1$ requires uninstalling packages $1, 5, 6$. Now only package $0$ remains installed.

Then installing package $4$ requires installing packages $1, 4$. At this point $0, 1, 4$ are installed.

Finally, uninstalling package $0$ uninstalls all packages.