시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 256 MB 91 34 14 25.000%

문제

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의 부모 정점을 의미한다.

세 번째 줄에는 N개의 정수가 주어진다. i번째 수는 정점 i의 색깔을 의미한다.

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

쿼리는 한 줄에 하나씩 쿼리의 종류를 나타내는 X(1 ≤ X ≤ 2)와 음이 아닌 정수 k가 주어진다. 쿼리에서 처리할 정점의 번호 a는 (k ⊕ lst)이며, a는 1 이상 N 이하이다. ⊕는 배타적 논리합을 의미한다. lst는 가장 최근에 처리한 2번 쿼리의 결과를 의미하고, 초깃값은 0이다.

출력

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

예제 입력 1

5 4
5 2 2 1
1 3 2 3 3
1 4
2 1
2 0
1 1
2 6
1 7
2 1
1 1

예제 출력 1

3
3
2
2

https://www.acmicpc.net/problem/17469 에 있는 예제와 동일한 입력이다.

출처