트리 배치

시간 제한10초메모리 제한64 MB

요약

노드를 B개 이하씩 묶을 때 루트에서 단말까지 거치는 블록 수의 최댓값이 가장 작아지는 값을 모든 루트마다 구합니다.

난이도: 어려움10점 중 8점
유형: 동적 계획법, 트리, 그리디
정답자: 아직 제출이 없습니다

문제

트리는 컴퓨터 과학에서 널리 쓰는 자료구조이다. 트리 구조 자체는 단순하지만 오늘날의 컴퓨터 구조와는 잘 맞지 않는다. 메모리는 1차원 배열로 볼 수 있는데 트리는 1차원 구조가 아니라서, 트리를 메모리에 올릴 때 캐시 효율이 문제가 된다. 캐시에 들어 있는 데이터는 더 빨리 읽는다. 캐시 성능이 좋은 배치를 생각해 보자.

배치 비용은 다음과 같이 정의한다. 메모리는 블록으로 나뉘고, 한 블록에는 트리의 노드를 최대 $B$ 개까지 저장한다. 어떤 블록의 데이터를 읽으면 그 블록의 데이터가 모두 캐시에 올라가고, 그 블록에 속한 데이터는 더 빨리 읽는다. 노드 $v$ 를 읽은 다음 노드 $u$ 를 읽는 비용은 $u$ 와 $v$ 가 같은 블록에 있으면 $0$ , 아니면 $1$ 이다. 처음에 캐시는 비어 있으므로 경로에서 맨 처음 읽는 노드의 비용은 항상 $1$ 이다. 경로 $v_1, v_2, \dots, v_n$ 의 비용은 이 순서대로 노드를 읽을 때 드는 비용의 합이다. 트리의 배치 비용은 루트에서 각 단말 노드까지 가는 경로의 비용 중 최댓값이다. 단말 노드는 루트를 기준으로 자식이 없는 노드이고, 노드가 하나뿐인 트리에서는 루트가 곧 단말 노드이다.

아래 그림은 노드가 10개인 트리를 $B = 4$ , 노드 1을 루트로 두고 배치한 예이다. 테두리 하나가 블록 하나를 나타낸다. 왼쪽 배치는 비용이 $3$ 이라서 최적이 아니고, 오른쪽 배치는 최적 비용 $2$ 를 달성한다.

블록 배치 예시

트리가 주어질 때, 각 노드 $i$ 를 루트로 삼았을 때의 최소 배치 비용을 구하라.

입력

입력은 여러 테스트 케이스로 이루어진다. 각 테스트 케이스의 첫 줄에는 정수 $N$ 과 $B$ 가 공백 하나를 사이에 두고 주어진다 ( $1 \le N \le 100000$ , $1 \le B \le N$ ). 다음 $N - 1$ 개의 줄에는 정수가 하나씩 주어진다. $i$ 번째 정수 $p_i$ ( $1 \le p_i \le i$ )는 노드 $i + 1$ 과 노드 $p_i$ 가 연결되어 있다는 뜻이다. 노드 번호는 $1$ 번부터 $N$ 번까지이다.

마지막 테스트 케이스 다음 줄에는 $0$ 두 개가 주어진다. 이 줄은 처리하지 않는다.

출력

각 테스트 케이스마다 먼저 Case x: 를 한 줄에 출력한다. $x$ 는 $1$ 부터 시작하는 테스트 케이스 번호이다. 이어서 $N$ 개의 줄을 출력한다. $i$ 번째 줄에는 노드 $i$ 를 루트로 삼았을 때의 최소 배치 비용을 출력한다.

예제2

예제 1

입력

예상 출력

Case 1:
3
2
3
Case 2:
2
2
2
Case 3:
2
2
2
2
2
2
2
2
2
3

예제 2

입력

예상 출력

Case 1:
1
Case 2:
2
2
Case 3:
1
1
Case 4:
1
1
1
Case 5:
1
1
1
1