All submissions for this problem are available.
The human army has proved itself against the mighty aliens by winning the Great War.
But even in times of peace, the army should remain alert and disciplined.
The army has N soldiers. The soldiers are numbered from 1 to N. The army has a superiority hierarchy. Every soldier has one immediate superior. The superior of a superior of a soldier is also a superior to that soldier. So, a soldier may have one or more superiors but only one immediate superior.
As a exercise to determine the efficiency of the army, the following drill has been designed.
You are given a list of orders. Each order is of the form "Type space ID"
where Type is either 1,2 or 3 and ID is a number S (1<=S<=N) that denotes a soldier.
There are three types of orders:
All the soldiers who have S as one of their superior will wake up.
All the soldiers who have S as one of their superior will go to sleep.
Count and output the number of soldiers who are awake and have S as one of their superior.
NOTE: Among all soldiers there is one soldier who does not have any superior. He is the commander of the whole army.
The first line contains N, the number of soldiers. The next line contains N space separated integers. The ith integer represents the immediate superior of the ith soldier.
The immediate superior of the commander of the army will be '0'.
The third line contains Q, the number of orders.
Each of the next Q lines contain two integers, the type of order and S.
For each Type-3 order, output the number of soldiers who are awake and have the given soldier as their superior.
- 1 ≤ N ≤ 100000
- 1 ≤ Q ≤ 100000
- 1 ≤ type ≤ 3
- 1 ≤ S ≤ N
A soldier cannot be his own superior.
Input: 3 2 0 1 3 3 1 2 1 3 1 Output: 1 0
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYP3|
Fetching successful submissions
If you are still having problems, see a sample solution here.