KOI 나라는 \(N\)개의 도시로 이루어져 있으며, 각 도시는 \(1, 2, \dots , N\)의 번호가 매겨져 있다. \(1\)번 도시는 KOI 나라의 수도이다.

KOI 나라에는 \(N − 1\)개의 양방향 도로가 있으며, \(2 ≤ i ≤ N\)인 모든 \(i\)에 대해, \(i\)번 도시는 \(P_i\)번 도시와 양방향 도로로 연결되어 있다. 이 때, \(P_i < i\)를 만족하며, \(i\)번 도시와 \(P_i\)번 도시를 잇는 도로의 일일 이용량은 \(W_i\)이다.

\(1\)번 도시(수도)에서 \(v\)번 도시를 잇는 단순 경로 위에 \(u\)번 도시가 있다면, 우리는 \(u\)번 도시가 \(v\)번 도시를 통제한다고 정의한다. \(i\)번 도시의 관리 구역은, \(i\)번 도시가 통제하는 모든 도시의 집합으로 정의된다. 이에 따라, \(1\)번 도시의 관리 구역은 모든 도시이며, \(1 ≤ i ≤ N\)인 모든 \(i\)에 대해 \(i\)번 도시는 \(i\)번 도시의 관리 구역에 속한다. KOI 나라의 도로망을 \(1\)번 도시를 루트로 한 트리 구조로 보았을 때, \(i\)번 도시의 관리 구역은 \(i\)번 도시의 서브트리와 일치한다.

KOI 나라의 각 도시에서 축제를 열려고 한다. 평소에는 모든 도로의 통행료가 무료이지만, 축제가 열릴 때에는 축제를 여는 비용을 충당하기 위해 일부 도로에서 통행료를 걷으려고 한다.

\(i\)번 도시에서 축제가 열린다면, 도로 중 일부를 선택하여 통행료를 걷을 수 있다. 일일 통행료 수익은 통행료를 걷는 도로들의 일일 이용량의 합이다. 단, 사람들의 불만을 줄이기 위해 선택하는 도로들은 다음 두 조건을 만족해야 한다:

• KOI 나라의 임의의 두 도시를 잇는 단순 경로 위에는, 통행료를 걷는 도로가 \(K\)개 이하로 존재해야 한다.
• 통행료를 걷는 도로가 잇는 두 도시가 모두 \(i\)번 도시의 관리 구역에 있어야 한다.

\(1 ≤ i ≤ N\)인 모든 \(i\)에 대해, \(i\)번 도시에서 축제가 열린다고 가정할 때 일일 통행료 수익의 최댓값을 구하는 프로그램을 작성하라.

• 주어지는 모든 수는 정수이다.
• \(1 ≤ K < N ≤ 300\,000\)
• \(2 ≤ i ≤ N\)인 모든 \(i\)에 대해 \(1 ≤ P_i < i\)
• \(2 ≤ i ≤ N\)인 모든 \(i\)에 대해 \(0 ≤ W_i ≤ 10^9\)

첫 번째 줄에 \(N\)와 \(K\)가 공백을 사이에 두고 주어진다.

이후 \(N − 1\)개의 줄이 주어진다. \(i − 1\) (\(2 ≤ i ≤ N\))번째 줄에는 \(P_i\)와 \(W_i\)가 공백을 사이에 두고 주어진다.

총 \(N\)개의 줄을 출력한다. \(i\) (\(1 ≤ i ≤ N\))번째 줄에는 \(i\)번 도시에서 축제가 열릴 때 일일 통행료 수익의 최댓값을 출력한다.

riseoj 작성

출처 올림피아드 > 한국정보올림피아드 > KOI 2025 > 2차 대회 > 고등부 4번