헛간에서 도망치기

농부 존(Farmer John)의 농장에 젖 짜는 시간이 되었는데, 소들이 모두 도망가 버렸다! 농부 존은 소들을 모두 모아야 하며, 수색에 당신의 도움이 필요하다.

FJ의 농장은 1...N으로 번호가 붙은 N개 (1 <= N <= 200,000)의 목초지가 N - 1개의 양방향 길로 연결된 형태이다. 헛간은 목초지 1에 있으며, 헛간에서 어떤 목초지로든 갈 수 있다.

FJ의 소들은 오늘 아침에는 각자의 목초지에 있었지만, 지금은 어디로 도망갔는지 알 수 없다. FJ가 아는 것은 소들이 헛간에서 멀어지는 방향으로만 도망치고, 게을러서 L보다 먼 거리는 달리지 않는다는 것이다. 각 목초지에 대해, FJ는 그 목초지에서 출발한 소가 도착했을 수 있는 서로 다른 목초지가 몇 개인지 알고 싶어 한다.

참고: 거리 값을 저장하려면 64비트 정수(Pascal의 int64, C/C++의 long long, Java의 long)가 필요하다.

첫째 줄: 두 정수 N과 L (1 <= N <= 200,000, 1 <= L <= 10^18)

둘째 줄부터 N번째 줄까지: i번째 줄에 두 정수 p_i와 l_i가 주어진다. p_i (1 <= p_i < i)는 목초지 i와 헛간 사이의 최단 경로에서 첫 번째 목초지이고, l_i (1 <= l_i <= 10^12)는 그 길의 길이이다.

첫째 줄부터 N번째 줄까지: 한 줄에 수 하나씩 출력한다. i번째 줄의 수는 헛간(목초지 1)에서 엄격히 멀어지는 길들만 따라가되 총 길이가 L을 넘지 않게 하여 목초지 i에서 도달할 수 있는 목초지의 수이다.

riseoj 작성

출처 올림피아드 > USACO > 2012-2013 > December > Gold