Company Culture 5
Time limit2sMemory limit512 MB
A supervisor tree supports turning all subordinates of a worker on or off, and counting how many subordinates of a worker are currently on. Initially only the computer of node 1 is on.
- Level
Medium7 of 10
- Topics
- Tree, DFS, Segment tree, Implementation
- Solved
- No attempts yet
Problem
A company employs N workers, numbered 1 to N. The company has a hierarchical structure, and every worker except the CEO has exactly one direct supervisor. The direct supervisor's direct supervisor is also a supervisor, and the direct supervisor's supervisor is also a supervisor. So every worker except the CEO has at least one supervisor and exactly one direct supervisor. The person with no supervisor is the CEO.
The company's culture can be described by the following queries. Initially, the computer is on.
1 i: every worker who has worker i as a supervisor turns their computer on.2 i: every worker who has worker i as a supervisor turns their computer off.3 i: print the number of workers who have worker i as a supervisor and whose computer is on.
Input
The first line gives the number of workers N (1 ≤ N ≤ 100,000).
The second line gives each worker's supervisor number. The i-th integer is the number of worker i's direct supervisor. The CEO has number 1, and a supervisor number of 0 is given for the CEO.
The third line gives the number of queries M (1 ≤ M ≤ 100,000).
M lines follow, each giving a query. (1 ≤ i ≤ N)
Output
Print the result of each type 3 query, one per line.