問題
♬ I wonder how, I wonder why. ♬
-Fool's Garden의 <Lemon Tree> 중
노란 레몬 나무가 한 그루 보인다.
레몬 나무는 정점이 N개이며 1번 정점이 루트인 트리이다.
(트리란 사이클이 없는 연결 그래프를 의미한다.)
처음에는 나무에 레몬이 한 개도 열려있지 않아 노랗지 않다.
이 트리의 정점에 한 개씩 레몬이 열리기 시작하면서 나무가 점점 노랗게 보이는 것이다.
한 정점에는 최대 한 개의 레몬이 열리고 따라서 최대 N개의 레몬이 열릴 수 있다.
어떤 레몬 나무의 노란 정도는 다음과 같은 정점 쌍 (u, v)의 개수와 같다.
u와 v 모두에 레몬이 열려 있다.
u는 v의 조상 정점이다.
레몬이 k개 열려 있는 레몬 나무 중 가장 덜 노란 나무의 노란 정도를 0에서 N까지의 모든 k에 대해 구해보자.
輸入
정점의 개수 N이 첫 줄에 주어진다. (1 <= N <= 200 000)
이후 N-1 줄에 걸쳐 2번 정점부터 N번 정점까지 각 정점의 부모가 주어진다.
<Subtask>
#1 (20점) : N <= 20
#2 (20점) : N <= 500
#3 (60점) : 추가적인 제한 조건이 없다.
輸出
한 줄에 레몬이 0개 달렸을 때 최소 노란 정도부터 N개 달렸을 때의 최소 노란 정도까지 N+1개의 수를 공백으로 구분하여 출력한다.
範例 #1
3
1
1
0 0 0 2
範例 #2
3
3
1
0 0 1 3
標籤
來源
2023 KAIST Spring, azberjibiou | songc
需要登入才能撰寫程式碼。