시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 256 MB132454238739.571%

문제

N개의 정점으로 구성된 트리가 있다. 각 정점은 1번부터 N번까지 번호가 매겨져있고, 1 이상 10만 이하의 자연수로 표현되는 색깔을 하나 갖고 있다. 루트는 1번 정점이고, 트리이기 때문에 임의의 서로 다른 두 정점을 잇는 경로는 반드시 한 개 존재한다.

정점 u와 v를 잇는 경로가 존재하면 u에서 v로 갈 수 있다고 하자.

여러분은 아래 두 가지 쿼리를 처리해야 한다.

  • 1 a : 정점 a와 a의 부모 정점을 연결하는 간선을 제거한다. (해당 간선이 존재하는 경우에만 주어진다.)
  • 2 a : 정점 a에서 갈 수 있는 정점들만 보았을 때, 색깔의 종류의 개수를 출력한다.

입력

첫 번째 줄에는 정점의 개수 N(1 ≤ N ≤ 100,000)과 2번 쿼리의 개수 Q(1 ≤ Q ≤ 1,000,000)가 주어진다.

다음 N-1개 줄의 i번째 줄에는 정점 i+1의 부모 정점을 나타내는 정수 p(1 ≤ p ≤ N)가 주어진다.

다음 N개 줄의 i번째 줄에는 정점 i의 색깔을 나타내는 정수 c(1 ≤ c ≤ 100,000)가 주어진다.

다음 N+Q-1개의 줄에는 여러분이 처리해야 할 쿼리가 주어지는데, 1번 쿼리는 N-1개, 2번 쿼리는 Q개 주어진다.

쿼리는 한 줄에 하나씩 쿼리의 종류를 나타내는 X(1 ≤ X ≤ 2)와 쿼리에서 처리할 정점의 번호 a(1 ≤ a ≤ N)가 주어진다.

입력은 모두 자연수로 주어진다.

출력

Q개의 2번 쿼리에 대한 답을 순서대로 한 줄에 하나씩 출력한다.

예제 입력 1

5 4
5
2
2
1
1
3
2
3
3
1 4
2 1
2 3
1 2
2 5
1 5
2 3
1 3

예제 출력 1

3
3
2
2

출처

  • 문제의 오타를 찾은 사람: jh05013
  • 문제를 만든 사람: jhnah917
  • 데이터를 추가한 사람: kyo20111
  • 문제를 검수한 사람: ryute