6174 : 트리 색칠 쿼리
•시간제한: 2.000 S
•메모리제한: 256 MB
•제출: 0
•통과: 0
•만든사람: suakii
문제 설명
트리의 각 노드에 초기 색상이 주어집니다. 특정 서브트리의 모든 노드의 색상을 변경하는 연산과 특정 서브트리에 존재하는 서로 다른 색상의 가짓수를 구하는 연산을 효율적으로 처리하는 프로그램을 작성하시오.
입력 설명
첫째 줄에 노드의 개수 N과 쿼리의 개수 Q (1 ≤ N, Q ≤ 100,000)가 주어집니다.
둘째 줄에 N개의 초기 색상이 공백으로 구분되어 주어집니다.
셋째 줄부터 N-1개의 줄에 트리 간선 정보 u, v가 주어집니다.
그 다음 Q개의 줄에 쿼리가 주어집니다.
-
-
둘째 줄에 N개의 초기 색상이 공백으로 구분되어 주어집니다.
셋째 줄부터 N-1개의 줄에 트리 간선 정보 u, v가 주어집니다.
그 다음 Q개의 줄에 쿼리가 주어집니다.
-
1 u color: u번 노드의 서브트리 모든 노드 색상을 color로 변경합니다.-
2 u: u번 노드의 서브트리에 존재하는 서로 다른 색상의 가짓수를 출력합니다.출력 설명
2번 쿼리가 주어질 때마다 서로 다른 색상의 수를 한 줄씩 출력합니다.
입력 예시
COPY
복사되었습니다!
복사되었습니다!
5 4
1 2 1 3 2
1 2
1 3
2 4
2 5
2 1
1 2 4
2 1
2 2
출력 예시
COPY
복사되었습니다!
복사되었습니다!
3
2
1