13209 - 검역소

 

 

step 1

검역소를 설치하는 것은 트리에서 간선을 끊는 것으로 생각할 수 있습니다. 즉 $K$개의 간선을 끊었을 때 각 트리에 있는 사람들 수의 합의 최대값을 최소로 하는 문제입니다. 문제를 살짝 바꿔서 "각 트리에 최대 $X$명의 사람이 있을 수 있다고 하면 적어도 몇 개의 다리를 끊어야 하는가"로 생각해 봅시다. $X$가 커질수록 끊어야 하는 다리의 수는 적어집니다. 따라서 이분 탐색으로 $X$값을 찾을 수 있습니다.

step 2

bridge[i] = i번째 정점을 루트로 생각했을 때 끊어야 하는 다리의 최소값

person[i] = bridge[i]를 최소로 만들었을 때 i번째 정점이 속한 트리에 있는 사람 수.

 

이 두 dp를 채운다고 생각합니다. 어떤 정점이 시작점이여도 답은 바뀌지 않으니 1번 정점을 루트로 생각합시다. dfs를 돌리면서 각 정점을 방문합니다. 그리고 정점을 빠져나올 때 dp값을 채워줍니다.

step 3

i의 자식 정점들을 $a_1, a_2, ..., a_n$이라 합시다. 편의상 person[$a_1$] $\le$ person[$a_2$] $\le ... \le$ person[$a_n$]이라 합시다. 저희는 person[i] $\le X$를 만족하면서 최대한 적은 다리를 끊어야 합니다. 그럼 i번 도시에 있는 사람에 person[$a_1$]부터 쭉 더해주다가 더이상 더하지 못할 때 이 이후에 있는 모든 다리를 끊어버리면 됩니다. 그럼 person[i]와 bridge[i]는 쉽게 구할 수 있습니다.

코드

#include<stdio.h>
#include<vector>
#include<algorithm>
using namespace std;
vector<long long int> v[200000];
long long int b[200000],ch[200000],bb[200000],cnt=0;
long long int dfs(long long int i,long long int xx) {
	long long int j;
	vector<long long int> vv;
	ch[i] = 1;
	for (j = 0; j < v[i].size(); j++) {
		if (ch[v[i][j]] == 0) { vv.push_back(dfs(v[i][j], xx)); }
	}
	long long int st = vv.size(),x=b[i];
	for (j = 1; j <= st; j++) bb[j] = vv[j-1];
	vv.clear();
	sort(bb + 1, bb + st + 1);
	for (j = 1; j <= st; j++) {
		if (x + bb[j] <= xx) x += bb[j]; else break;
	}
	cnt += st - j + 1;
	return x;
}
int main() {
	long long int n,tt,m,i,s,e,mi,max=-1;
	scanf("%lld", &tt);
	while (tt--) {
		scanf("%lld %lld", &n, &m);
		max = -1;
		for (i = 1; i <= n; i++) { scanf("%lld", &b[i]); if (max < b[i]) max = b[i]; }
		for (i = 1; i < n; i++) {
			long long int x, y;
			scanf("%lld %lld", &x, &y);
			v[x].push_back(y);
			v[y].push_back(x);
		}
		s = max;
		e = 3223300000000000000LL;
		while (s < e) {
			mi = (s + e) / 2;
			cnt = 0;
			for (i = 1; i <= n; i++)ch[i] = 0;
			dfs(1, mi);
			if (cnt <= m) e = mi; else s = mi + 1;
		}
		printf("%lld\n", s);
		for (i = 1; i <= n; i++) v[i].clear();
	}
	return 0;
}