충분한 소 먹이

목축업자 태승은 자신이 기르는 소들이 농장 내 여러 초원 사이를 자주 이동하는 것을 알게 되었습니다. 이를 고려하여 그는 각 초원에 원래부터 길렀던 소뿐만 아니라 인근 초원에서 건너오는 소들을 위해 충분한 양의 풀을 심고 싶어 합니다.

태승의 농장은 N개(1 <= N <= 100,000)의 초원으로 이루어진 거대한 농장입니다. 일부 초원은 양방향의 오솔길로 연결되어 있으며 (전체적으로 총 N-1개의 오솔길), 두 초원 i와 j를 유일하게 연결하는 오솔길을 만들어 농장을 설계했습니다. 초원 i에는 C(i) 마리의 소를 방목하고 있지만, 소들은 때때로 최대 K개 (1 <= K <= 20)의 오솔길을 따라 다른 초원으로 이동하기도 합니다.

태승은 각 초원 i에 최대한 많은 소, 즉 M(i)를 먹일 수 있을 만큼의 풀을 심고 싶어합니다. M(i)는 최대 K개의 오솔길을 따라 초원 i에 도달할 수 있는 소들의 수입니다. 태승의 농장 구조와 각 들판 i의 C(i) 값을 고려하여 모든 초원 i에 대해 M(i)를 계산해주세요.

• 줄 1: 두 개의 띄어쓰기로 구분된 정수, N과 K.
• 줄 2..N: 각 줄에는 두 개의 띄어쓰기로 구분된 정수, i와 j (1 <= i,j <= N)로 들판 i와 j가 직접적으로 오솔길로 연결되어 있음을 나타냅니다.
• 줄 N+1..2N: N+i 번째 줄에 정수 C(i)가 있습니다. (0 <= C(i) <= 1000)

• 줄 1..N: 줄 i에는 M(i)의 값을 포함해야 합니다.