회사 문화 5
시간 제한2초메모리 제한512 MB
감독 관계를 나타내는 트리에서 한 직원의 모든 부하 직원 컴퓨터를 켜거나 끄고, 특정 직원의 부하 중 컴퓨터가 켜진 사람 수를 구한다. 처음에는 1번 직원의 컴퓨터만 켜져 있다.
문제
총 N명의 직원이 재직 중인 회사가 있고, 각 직원은 1번부터 N번까지 번호가 매겨져 있다. 이 회사는 수직 구조를 가지고 있고, 대표를 제외한 모든 직원은 한 명의 직속 상사를 갖고 있다. 직속 상사의 직속 상사도 상사이고, 직속 상사의 상사도 상사이다. 따라서 대표를 제외한 모든 직원은 한 명 이상의 상사를 가지고 있고, 한 명의 직속 상사를 갖고 있다. 상사가 없는 사람은 대표이다.
이 회사가 가지고 있는 문화는 아래와 같은 쿼리로 나타낼 수 있다. 가장 처음에 컴퓨터는 켜져 있는 상태이다.
1 i: i번 직원을 상사로 가지고 있는 모든 직원은 컴퓨터를 켠다.2 i: i번 직원을 상사로 가지고 있는 모든 직원은 컴퓨터를 끈다.3 i: i번 직원을 상사로 가지고 있는 직원 중에서 컴퓨터가 켜져 있는 사람의 수를 출력한다.
입력
첫째 줄에 직원의 수 N (1 ≤ N ≤ 100,000)이 주어진다.
둘째 줄에는 각 직원의 상사 번호가 주어진다. i번째 정수는 i번 직원의 직속 상사 번호이다. 대표의 번호는 1번이고, 상사 번호로 0이 주어진다.
셋째 줄에 쿼리의 수 M (1 ≤ M ≤ 100,000)이 주어진다.
넷째 줄부터 M개의 줄에 쿼리가 주어진다. (1 ≤ i ≤ N)
출력
3번 쿼리의 결과를 한 줄에 하나씩 출력한다.