평원에는 눈이 내렸고, 매년 겨울이 시작될 때마다 그랬던 것처럼 정올이는 눈사람을 만들고 있다! 대부분의 경우 정올이는 자신의 조각품을 최대한 실제 사람처럼 보이게 만들기 위해 노력한다. 하지만 올해는 예술적 영감을 받아 좀 더 추상적인 방식을 추구하기로 결심하고, 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에 있는 색의 종류 개수를 의미한다. 정올이의 질의에 따라 해당하는 눈덩이의 서브트리에 해당하는 눈덩이들의 다채로움 값의 합을 알아보자.

#4130 upload 3 done 2 how_to_reg 2 call_split Subtask

Bessie's Snow Cow timer 2s memory 512MB

#4130
Subtask

Bessie's Snow Cow 2s 512MB