BOJ 33626 나는 뱀파이어

문제 링크입니다.

문제 요약

정점 $N$개의 트리에서 $M$개의 정점을 선택해 말을 놓습니다. 말들은 루트를 향해 1초에 한 칸씩 올라옵니다. 루트를 제외한 모든 정점을 적어도 한 말이 방문하기 위해 필요한 최소 시간을 구하세요.

풀이

모든 리프 노드를 선택해야 하는 것은 자명합니다. 중간 노드에 말을 두면 리프 노드의 말이 도착하기 오래 걸리는 정점을 미리 방문하는 효과가 있겠죠.

$T$초 안에 모든 정점을 방문하고 싶다고 합시다. 각 말이 자신의 위로 $T$개의 칸을 색칠한다고 생각하면, 리프 노드부터 올라가면서 색칠이 안 된 정점이 나올 때마다 말을 올려두는 것이 말을 최소 개수로 쓴다는 사실을 알 수 있습니다. 이러한 작업은 DFS 돌리면 ${\cal O}(N)$에 가능합니다.

따라서 $T$에 대한 이분 탐색을 수행해 $M$개 이하의 말로 모든 정점을 칠할 수 있는 최소 시간을 구하면 ${\cal O}(N \lg N)$에 문제를 해결할 수 있습니다.

코드

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using pll = pair<ll, ll>;
 
int n, m, root, cnt;
vector<int> e[101010];

int dfs(int now, int pre, int k){
	int ret = k+1;
	for(auto nxt : e[now]){
		if(nxt == pre) continue;
		ret = min(ret, dfs(nxt, now, k)+1);
	}
	if(ret > k && now != root){
		ret = 0;
		cnt++;
	}
	return ret;
}

bool solve(int mid){
	cnt = 0; dfs(root, 0, mid);
	return cnt <= m;
}

int main(){
	cin.tie(0);cout.tie(0);ios::sync_with_stdio(false);
	cin >> n >> m >> root; for(int i = 1; i < n; i++){
		int u, v; cin >> u >> v; e[u].push_back(v); e[v].push_back(u);
	}
	int l = 0, r = n;
	while(l < r){
		int mid = l+r>>1;
		if(solve(mid)) r = mid;
		else l = mid+1;
	}
	if(l == n) cout << -1;
	else cout << l+1;
}