정올국은 N개의 도시들이 트리 형태로 연결되어 있는 모양이다. i번째 도로는 A_i와 B_i번 도로를 연결한다. 또한, 각 도시에는 1~M 사이의 특산물이 정해져 있어, i번째 도시는 C_i의 특산물을 만든다.

정올국의 독재자인 준혁이는 어느 한 곳을 수도로 정해, 특별한 도시들에서 특산물을 뇌물로 받으려 한다. 도시 x가 "특별한 도시"이기 위해서는, 수도에서 x까지 이동하기 위해 지나야 하는 간선의 개수가 d개일 때, 어떠한 다른 도시 y도 수도에서 이동하기 위한 간선의 개수가 정확히 d개이면 안된다.

아직 수도를 정하지 못한 준혁이는 어느 한 곳을 수도로 정해 그 도시를 기준으로 특별한 도시들에서 모두 특산물을 받았을 때, 서로 다른 특산물의 개수를 구하고 싶다. 준혁이의 충실한 부하인 여러분은 준혁이를 위해 1~N까지의 각 도시들을 수도로 했을 때 받을 수 있는 서로 다른 특산물의 개수를 모두 구해주자.

2<=N<=200000, 1<=M<=N

Subtask 1 (4점) : N<=2000

Subtask 2 (32점) : M=1

Subtask 3 (32점) : N=M, C_i=i

Subtask 4 (32점) : 추가 제한 조건 없음

#5021 upload 4 done - how_to_reg - call_split サブタスク

특별한 도시 timer 2s memory 256MB

#5021
サブタスク

특별한 도시 2s 256MB