문제
정올국은 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점) : 추가 제한 조건 없음
입력
다음과 같은 형식으로 입력이 주어진다.
N M
A_1 B_1
.
.
.
A_N−1 B_N−1
C_1 · · · C_N
출력
N개의 줄에 걸쳐 i번째 줄에는 i번 도시를 수도로 했을 때의 답을 출력하시오.
예제 #1
5 4
1 2
2 3
3 4
3 5
1 2 1 2 4
2
0
1
1
1
예제 #2
7 1
1 2
2 3
3 4
4 5
5 6
6 7
1 1 1 1 1 1 1
1
1
1
0
1
1
1
예제 #3
10 10
2 6
5 8
10 8
1 4
10 6
4 5
10 7
6 9
3 7
1 2 3 4 5 6 7 8 9 10
4
3
4
2
0
2
2
0
3
2
예제 #4
22 12
9 6
12 13
4 20
21 22
3 19
2 9
6 18
18 11
18 3
16 2
6 4
3 17
16 10
8 16
22 1
16 14
15 8
9 21
2 12
21 5
12 7
1 1 4 8 4 11 7 6 7 11 6 11 10 4 7 5 3 12 9 6 12 2
2
0
1
1
1
1
1
0
0
1
2
0
1
1
2
0
2
1
2
3
0
0
로그인해야 코드를 작성할 수 있어요.