Educational Codeforces Round 136 (Rated for Div. 2) - D

Result

 

 

D. Reset K Edges

Problem

D. Reset K Edges

Problem - 1739D - Codeforces

 n개의 정점으로 이루어진 루트가 있는 트리가 주어진다. 정점들은 1부터 n까지 번호가 붙어 있으며, 루트는 1번 정점이다.

 

 당신은 다음의 작업을 최대 k번 수행할 수 있다:

• 정점 v가 정점 u의 부모인 간선 (v, u)를 선택한다;
• 간선 (v, u)를 지운다;
• 간선 (1, u)를 추가한다 (즉, 정점 u와 그 서브트리를 루트의 자신으로 만든다). 

 

 트리의 높이는 정점들의 깊이 중 최댓값이며, 정점의 깊이는 루트부터 해당 정점까지 가는 경로 상의 간선 개수이다. 예를 들어, 정점 1은 루트이기 때문에 깊이가 0이고, 그 자식들은 깊이가 1이다.

 

 만들 수 있는 트리 중 가장 낮은 높이는 몇일까?

 

 

Input

 첫째 줄에는 테스트 케이스의 개수를 나타내는 하나의 정수 t($1 \leq t \leq 10^4$)가 주어진다.

 

 각 테스트 케이스의 첫째 줄에는 트리의 정점의 개수와 수행할 수 있는 작업의 최대 횟수를 나타내는 두 정수 n과 k($2 \leq n \leq 2 \cdot 10^5; 0 \leq k \leq n - 1$)가 주어진다.

 

 각 테스트 케이스의 둘째 줄에는 i번째 정점의 부모를 나타내는 n-1 개의 정수 $p_2, p_3, ..., p_n (1 \leq p_i < i)$이 주어진다. 정점 1은 루트이다.

 

 모든 테스트 케이스의 n의 총합은 $2 \cdot 10^5$을 넘지 않는다.

 

 

Output

 각 테스트 케이스에 대하여, 최대 k번의 작업을 수행하여 만들 수 있는 트리 중 가장 낮은 높이를 나타내는 하나의 정수를 출력하여라.

 

 

Example

input	output
5 5 1 1 1 2 2 5 2 1 1 2 2 6 0 1 2 3 4 5 6 1 1 2 3 4 5 4 3 1 1 1	2 1 5 3 1

 

 

Tutorial

 문제를 보자마자 이분탐색을 생각해 냈다면 성공이다.

 이 문제는 k번의 작업을 수행했을 때 만들 수 있는 가장 낮은 높이를 구하는 것보다, 높이가 주어졌을 때 해당 높이 이하의 트리를 만들기 위해 최소 몇번의 작업을 해야하는지를 구하는 것이 훨씬 쉽기 때문이다.

 

 기준 높이가 주어졌을 때, 기준 높이 이하의 트리를 만들기 위해 필요한 최소 작업 횟수는 어떻게 구할 수 있을까?

 기준 높이보다 높아지는 순간의 구간을 잘라서 루트에 붙여주면 된다. 그러나 여기서 높아지는 순간을 탐색하는 순서가 중요하다. 루트에서 시작해서 트리의 높이가 기준 높이보다 높아지는 순간 서브 트리를 자르면 작업 횟수를 최소화 할 수 없다. 말단 노드에서 시작해서 서브트의 높이가 (기준 높이 - 1)이 되는 순간 해당 서브트리를 루트의 자식으로 만들어줘야 최소 횟수로 작업을 진행할 수 있게 된다. 그리고 이 문제는 감사히도 큰 번호 노드가 작은 번호 노드의 부모가 되지 않기 때문에 번호가 큰 노드부터 1번 노드까지 살펴보면서 자연스럽게 말단노드부터 탐색을 할 수 있게 된다.

 

 

Solution

#include <iostream>

#define MAXN 200000

using namespace std;

int p[MAXN+10], h[MAXN+10];

int main()
{
    int t, n, k, i, l, m, r, cnt;

    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);

    cin >> t;
    while(t--){
        cin >> n >> k;
        for(i=2; i<=n; i++) cin >> p[i];

        l = 1;
        r = n;
        while(l < r){
            m = (l+r) / 2;

            for(i=1; i<=n; i++) h[i] = 0;
            cnt = 0;
            for(i=n; i>=2; i--){
                if(h[i] == m-1 && p[i] != 1) cnt++;
                else h[p[i]] = max(h[p[i]], h[i]+1);
            }

            if(cnt <= k) r = m;
            else l = m+1;
        }

        cout << l << '\n';
    }

    return 0;
}

 

 

마치며...

 실제로 2시간이라는 제한 시간이 있고, 이 문제를 4번으로 봤다면 급한 마음에 어땠을지 잘 모르겠지만, 이 문제는 Div. 2의 D에 들어가기에는 좀 쉽다는 생각이 들었다. 오히려 어제 풀었던 C번 문제가 훨씬 어려운 느낌이었다.

 만약 "마치며..."를 먼저 읽은 사람이 있다면 충분히 스스로 풀 수 있는 문제니 자신감을 가지고 풀어보기를 추천하다.