플래티넘 IV농부 존(Farmer John)은 자신의 소들이 근처 목초지 사이를 자주 오간다는 것을 알아챘다. 이를 고려하여, 존은 각 목초지에 처음부터 그곳에 있던 소들뿐만 아니라 근처 목초지에서 방문하는 소들까지 먹일 수 있을 만큼 충분한 풀을 심고 싶어 한다.
구체적으로, FJ의 농장은 N개의 목초지 (1 <= N <= 100,000)로 이루어져 있으며, 일부 목초지 쌍은 양방향 오솔길로 연결되어 있다 (오솔길은 총 N-1개). FJ는 임의의 두 목초지 i와 j 사이에 오솔길로 이루어진 유일한 경로가 존재하도록 농장을 설계했다. 목초지 i에는 C(i)마리의 소가 살고 있지만, 소들은 최대 K개의 오솔길을 건너 다른 목초지로 이동하기도 한다 (1 <= K <= 20).
FJ는 각 목초지 i에, 그곳에 모일 수 있는 소의 최대 수 M(i)를 먹일 만큼의 풀을 심고 싶어 한다. 즉, 최대 K개의 오솔길을 따라 이동하여 목초지 i에 도달할 수 있는 소의 수이다. FJ의 농장 구조와 각 목초지 i의 C(i) 값이 주어질 때, 모든 목초지 i에 대해 M(i)를 계산하는 것을 도와주자.
첫째 줄: 공백으로 구분된 두 정수 N과 K.
둘째 줄부터 N번째 줄까지: 각 줄에 공백으로 구분된 두 정수 i와 j (1 <= i,j <= N)가 주어지며, 목초지 i와 j가 오솔길로 직접 연결되어 있음을 나타낸다.
N+1번째 줄부터 2N번째 줄까지: N+i번째 줄에 정수 C(i)가 주어진다. (0 <= C(i) <= 1000)
첫째 줄부터 N번째 줄까지: i번째 줄에 M(i)의 값을 출력한다.
nearcows.in · 출력을 쓸 파일 nearcows.out6 2
5 1
3 6
2 4
2 1
3 2
1
2
3
4
5
615
21
16
10
8
11Input details: There are 6 fields, with trails connecting (5,1), (3,6), (2,4), (2,1), and (3,2). Field i has C(i) = i cows.
Output details: Field 1 has M(1) = 15 cows within a distance of 2 trails, etc.
riseoj 작성
출처 올림피아드 > USACO > 2011-2012 > February > Gold
