17469번 - 트리의 색깔과 쿼리

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