22306번 - 트리의 색깔과 쿼리 2

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번 쿼리에 대한 답을 순서대로 한 줄에 하나씩 출력한다.