트리의 색깔과 쿼리
시간 제한2초메모리 제한256 MB
루트 있는 트리에서 간선이 순차적으로 삭제될 때, 주어진 정점에서 도달 가능한 정점들이 가진 서로 다른 색의 수를 구한다.
문제
N개의 정점으로 구성된 트리가 있다. 각 정점은 1번부터 N번까지 번호가 매겨져 있고, 1 이상 100,000 이하의 자연수로 표현되는 색깔을 하나 갖고 있다. 루트는 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번 쿼리에 대한 답을 순서대로 한 줄에 하나씩 출력한다.