2454번: 트리 분할

https://www.acmicpc.net/problem/2454


$O(n)$

트리 내의 아무 정점에서 dfs탐색을 시작해보자.
이 문제는 탐색과정에서 (x,y)=(k+1개 커버 중 남은 개수, 분할 수) 정보만 가지고 해결할 수 있다.
* k+1개 커버 중 남은 개수란 앞으로 같은 묶음으로 포함할 수 있는 조상 정점들의 개수이다.
이게 가능한 이유는 다음과 같다.
현재 정점과 그 자식들을 포함한 트리의 가능한 (x,y) 해가 (x1,y1), (x2,y2) .. 있다고 해보자.
(xi,yi)와 (xj,yj) 중 어떤게 더 나은 해인지 판단하기 위해 다음 경우들을 따져보면 된다.
yi<yj일 때,
xi>xj 당연히 xi는 xj처럼 덜 쓸 수 있기때문에 전자가 유리하다.
xi<xj xi가 더 작지만 yi+1을 하여 xi=k>=xj 로 만들 수 있어 전자가 유리하다.
yi=yj일 때,
xi, xj 중 큰 쪽이 유리하다.
결론적으로 y가 작은 경우, 같다면 x가 큰 경우가 트리의 모양과 상관 없이 항상 유리하므로 해가 하나로 결정된다.

현재 정점의 (x,y)는 다음과 같이 결정한다.
자식들의 (x,y)를 (xi,yi)라고 표현하고 자식들의 yi 합을 s라고 하자.
가장 큰 자식들의 두 x 값을 p,q(p>q)라 하면
p+q>k+1인 경우 현재 정점을 조상과 같이 묶지 않고 자식들과 함께 묶음을 형성하여 s-1개의 묶음을 만들 수 있다. 이것은 가장 최선이다. -> (0,s-1) 리턴
그렇지 않고 p가 0보다 크다면 조상으로 나가는 묶음이 존재할 수 있으며(1이 아니면 그렇다) s개의 묶음을 만들 수 있다. -> (p-1,s)리턴
위 경우에 모두 해당되지 않는 경우는 각 자식들이 묶음의 끝이 되는 경우이다.
이 경우, 현재 정점으로부터 새로운 묶음을 형성해야 한다. -> (k,s+1) 리턴

처음 탐색을 시작한 정점이 리턴한 y값이 답이 된다.

#include<stdio.h>
#include<algorithm>
#include<vector>
using namespace std;
const int MAX_N = 3e5;
int n, k;
vector<int> adj[MAX_N + 1];
pair<int, int> dfs(int h, int p) {
    int m1, m2, s;
    m1 = m2 = s = 0;
    for (auto it : adj[h]) {
        if (it == p) continue;
        pair<int, int> p = dfs(it, h);
        m2 = max(m2, p.first);
        if (m1 < m2) swap(m1, m2);
        s += p.second;
    }
    if (m1 + m2 > k + 1) return{ 0,s - 1 };
    if (m1) return{ m1 - 1, s };
    return{ k, s + 1 };
}
int main() {
    scanf("%d %d", &n, &k);
    for (int i = 0, x, y; i < n - 1; i++) {
        scanf("%d %d", &x, &y);
        adj[x].push_back(y);
        adj[y].push_back(x);
    }
    printf("%d", dfs(1, -1).second);
    return 0;
}