NOI '15 P2 - Software Package Manager

View as PDF

Submit solution

Points: 20 (partial)
Time limit: 1.0s
Memory limit: 512M

Problem type

You'd like to design a package manager on your own, and thus you'd like to resolve the dependency problem among packages. If package A depends on package B, then we must install package B before package A. Likewise, if we'd like to remove package B, we also need to remove package A. You know the dependency relations among the packages, and you may assume all packages other than package 0 will rely on exactly one package (package 0 does not rely on any other packages). There are no cycles in the dependency relation (like A_1 depends on A_2, A_2 depends on A_3, ..., A_{m_1} depends on A_m but A_m depends on A_1), and of course no package depends on itself.

Now you'd like to know how many packages have their status changed upon installing or uninstalling a given package. Notice installing an installed package or uninstalling an uninstalled package will not change the status of any package.

Input Specification

The first line of the input is an integer n representing the number of packages. The packages are numbered beginning with 0.

The next line has (n-1) integers separated by a single space, representing the package that package 1,2,\ldots,n-2,n-1 depends on.

The next line contains an integer q representing the number of queries. In the following q lines, each line contains a query of form install x or uninstall x representing installing or uninstalling package x. You need to maintain the status of each package. Initially, all packages are uninstalled. You need to output how many packages will change the status after the step, and then apply the (un)installation.

Output Specification

The output consists of q lines. The i-th line is an integer representing the number of packages whose status change at step i.

Sample Input 1

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

Sample Output 1

3
1
3
2
3

Sample Input 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

Sample Output 2

1
3
2
1
3
1
1
1
0
1

Constraints

Test CasenqAdditional Constraints
1n = 5\,000q=5\,000
2
3n=100\,000q=100\,000we never uninstall a package
4
5n = 100\,000q = 100\,000the package that package i depends on is uniformly at random in [0,i-1]. The package installed or uninstalled at each query is uniformly at random in [0,n-1].
6
7
8
9n=100\,000q=100\,000
10
11
12
13
14
15
16
17
18
19
20

Comments

There are no comments at the moment.