페이지가 로드되지 않나요? 여기를 눌러보면 고쳐질 수도 있어요.
Placeholder

#4130
서브태스크

Bessie's Snow Cow 2s 512MB

문제

평원에는 눈이 내렸고, 매년 겨울이 시작될 때마다 그랬던 것처럼 정올이는 눈사람을 만들고 있다! 대부분의 경우 정올이는 자신의 조각품을 최대한 실제 사람처럼 보이게 만들기 위해 노력한다. 하지만 올해는 예술적 영감을 받아 좀 더 추상적인 방식을 추구하기로 결심하고, N개의 눈덩이(1\le N\le 10^5)를 N-1개의 가지로 연결하여 각 눈덩이 쌍 사이에 고유한 경로가 있도록 나무 모양의 조형물을 만들기로 결심했다.

정올이는 눈덩이 중 하나에 코를 추가하여 추상적인 눈사람의 머리를 표현했다. 그는 이 눈덩이를 1번 눈덩이로 지정했다. 시각적 흥미를 더하기 위해 그는 오래된 물통에 색 염료를 채우고 조각품에 뿌려서 눈덩이의 일부를 예술적인 방식으로 다양한 색으로 물들일 계획이다. 색은 1 \dots 10^5 범위의 정수로 식별되며, 정올이는 가능한 모든 색의 염료로 채워진 양동이를 무제한으로 가지고 있다.

정올이가 눈덩이에 염료 양동이를 뿌릴 때, 그 하위 트리에 있는 모든 눈덩이에도 같은 염료가 뿌려진다 (눈덩이 X가 눈덩이 Y에서 머리 눈덩이까지의 경로에 있다면 눈덩이 Y는 눈덩이 X의 하위 트리에 있다). 정올이는 각 색을 세심하게 뿌려서 눈덩이에 뿌려진 모든 색이 그대로 보이도록 한다. 예를 들어 눈덩이의 색이 [1,2,3]인데 정올이가 4번 색을 뿌린다면 눈덩이는 [1,2,3,4]의 색을 가지게 된다.

눈덩이에 몇 번 염료를 뿌린 후 정올이는 눈사람의 일부가 얼마나 다채로운지 알고 싶어졌다. 눈덩이 x의 '다채로움'은 눈덩이 x에 있는 색의 종류 개수를 의미한다. 정올이의 질의에 따라 해당하는 눈덩이의 서브트리에 해당하는 눈덩이들의 다채로움 값의 합을 알아보자.


입력

첫 번째 줄에 두 정수 N, Q가 주어진다 ( 1\le Q\le 10^5 ).

다음 N-1줄에는 가지로 연결된 두 눈덩이를 의미하는 두 정수 a,b가 주어진다 ( 1 \le a, b \le N ).

마지막 Q줄에는 쿼리가 주어진다.

  • 1\ x\ c : 정올이가 c 색의 염료를 x 눈덩이에 뿌렸다는 의미로, x 눈덩이의 서브트리에 해당하는 눈덩이들은 모두 c 색의 염료가 뿌려진다.

  • 2\ x : x 눈덩이의 서브트리에 해당하는 눈덩이들의 다채로움 값의 합을 출력한다.

  • 1\le x \le N

  • 1 \le c \le 10^5


출력

두 번째 유형의 쿼리에 대해 해당 하위 트리 내의 다채로움 값의 합을 출력한다.
오버플로를 방지하려면 64비트 정수 자료형을 사용해야 한다.


부분문제

번호 점수 조건
#114점

N\le 10^2, Q\le 2\cdot 10^2

#221점

N\le 10^3, Q\le 2\cdot 10^3

#365점

추가 제약 조건 없음


예제 

5 18
1 2
1 3
3 4
3 5
1 4 1
2 1
2 2
2 3
2 4
2 5
1 5 1
2 1
2 2
2 3
2 4
2 5
1 1 1
2 1
2 2
2 3
2 4
2 5
1
0
1
1
0
2
0
2
1
1
5
1
3
1
1

유형 1의 첫 번째 쿼리 후, 눈덩이 4는 색상 1로 염색됩니다.

유형 1의 두 번째 쿼리 후, 눈덩이 4와 5는 색상 1로 염색됩니다.

유형 1의 세 번째 쿼리를 실행한 후, 모든 눈덩이는 색상 1로 염색됩니다.



출처

USACO 2019 December Platinum

로그인해야 코드를 작성할 수 있어요.