베시의 눈소

농장에 눈이 내렸고, 매년 겨울이 시작될 때마다 그러듯 베시는 눈소(snow-cow)를 만들고 있다! 평소에 베시는 조각이 실제 소와 최대한 닮아 보이도록 애쓴다. 하지만 올해는 예술적 영감을 받아 더 추상적인 길을 택하기로 했고, \(N\)개의 눈덩이 \((1\le N\le 10^5)\)가 \(N-1\)개의 가지로 연결된 트리 모양의 조각을 만들기로 했다. 각 가지는 눈덩이 한 쌍을 연결하며, 모든 눈덩이 쌍 사이에는 유일한 경로가 존재한다.

베시는 눈덩이 하나에 코를 붙여서 그것이 추상적인 눈소의 머리를 나타내게 했다. 베시는 이 눈덩이를 1번 눈덩이로 지정한다. 시각적 재미를 더하기 위해, 베시는 오래된 우유 양동이에 색깔 염료를 채워 조각에 끼얹는 방식으로 일부 눈덩이를 예술적으로 다양한 색으로 물들일 계획이다. 색은 \(1 \ldots 10^5\) 범위의 정수로 구분되며, 베시에게는 가능한 모든 색의 염료가 담긴 양동이가 무제한으로 있다.

베시가 어떤 눈덩이에 염료 양동이를 끼얹으면, 그 눈덩이의 서브트리에 있는 모든 눈덩이에도 같은 염료가 끼얹어진다(눈덩이 \(x\)가 눈덩이 \(y\)에서 머리 눈덩이로 가는 경로 위에 있으면 눈덩이 \(y\)는 눈덩이 \(x\)의 서브트리에 있다). 베시는 각 색을 아주 조심스럽게 끼얹기 때문에, 눈덩이에 끼얹어진 모든 색은 계속 보이는 상태로 남는다. 예를 들어 어떤 눈덩이가 색 \([1,2,3]\)을 갖고 있는데 베시가 색 \(4\)를 끼얹으면, 그 눈덩이는 색 \([1,2,3,4]\)를 갖게 된다.

눈덩이에 염료를 몇 번 끼얹은 뒤, 베시는 눈소의 어떤 부분이 얼마나 다채로운지도 알고 싶어질 수 있다. 눈덩이 \(x\)의 "다채로움"은 눈덩이 \(x\)가 색 \(c\)로 칠해져 있는 서로 다른 색 \(c\)의 개수와 같다. 베시가 눈덩이 \(x\)에 대해 물어보면, \(x\)의 서브트리에 있는 모든 눈덩이의 다채로움 값의 합을 답해야 한다.

특정 시점마다 베시가 눈소의 다채로움을 알아내도록 도와주자.

문제 제공: Michael Cao and Benjamin Qi

점수 배점

\(Q\)는 아래에 정의된다.

• 테스트 케이스 2-3은 \(N\le 10^2, Q\le 2\cdot 10^2\)을 만족한다.
• 테스트 케이스 4-6은 \(N\le 10^3, Q\le 2\cdot 10^3\)을 만족한다.

문제 제공: Michael Cao and Benjamin Qi

첫째 줄에 \(N\)과 쿼리의 수 \(Q\)(\(1\le Q\le 10^5\))가 주어진다.

다음 \(N-1\)개의 줄에는 각각 공백으로 구분된 두 정수 \(a\)와 \(b\)가 주어지며, 이는 눈덩이 \(a\)와 \(b\)를 연결하는 가지를 나타낸다(\(1 \le a, b \le N\)).

마지막으로, 마지막 \(Q\)개의 줄에는 각각 쿼리가 하나씩 주어진다. 다음 형태의 쿼리는

1 x c

베시가 눈덩이 \(x\)에 색 \(c\)의 염료 양동이를 끼얹어 \(x\)의 서브트리에 있는 모든 눈덩이를 칠했음을 나타낸다. 다음 형태의 줄은

2 x

\(x\)의 서브트리에 있는 모든 눈덩이의 다채로움 값의 합을 묻는 쿼리이다. 물론 \(1\le x\le N\)이고 \(1\le c\le 10^5\)이다.

2번 유형의 각 쿼리에 대해, 해당 서브트리 내의 다채로움 값의 합을 출력한다. 오버플로를 피하기 위해 64비트 정수를 사용해야 함에 유의하라.

riseoj 작성

출처 올림피아드 > USACO > 2019-2020 > December > Platinum