28219 - 주유소

step 1

임의의 루트 하나를 잡습니다. 각 정점마다 (자신의 자식 정점들 중에서 주유소를 하나도 거치지 않고 갈 수 있는 가장 먼 정점까지의 거리 + 1)을 저장해 둡니다. 이때 해당 정점에 주유소가 없어야 합니다.

 

빨간색 정점이 주유소가 있는 정점입니다. 주유소가 있는 정점은 0을 적어줍니다.

step 2

만약 자기 바로 밑에 있는 정점들에 있는 수를 알고 있으면 해당 정점에 주유소를 만들어야 하는지 아닌지 알 수 있습니다. 가장 큰 두 수의 합이 $k$보다 크거나 같으면 반드시 주유소를 설치해야 합니다. 그렇지 않으면 설치하지 않는 것이 반드시 이득입니다.

 

이 사진에서 $k$가 5 미만이면 제일 위에 있는 정점은 주유소를 설치해야만 합니다. 그렇지 않으면 설치하지 않습니다.

만약 설치한다면 해당 정점에는 0을 적습니다.

설치하지 않는다면 해당 정점에는 (자기 바로 밑에 있는 정점들에 있는 수 중 최댓값 + 1)을 적습니다.

코드

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<algorithm>
#include<string.h>
#include<set>
#include<vector>
#include<queue>
using namespace std;
vector<int> v[300000];
int m,cnt=0;
int dfs(int i,int p) {
	int j,g1=0,g2=0;
	for (j = 0;j < v[i].size();j++) {
		if (v[i][j] == p) continue;
		int g = dfs(v[i][j], i);
		if (g > g1) {
			g2 = g1;
			g1 = g;
		}
		else if (g > g2) {
			g2 = g;
		}
	}
	if (g1 + g2 >= m) {
		g1 = 0;
		g2 = 0;
		cnt++;
		return 0;
	}
	return g1 + 1;
}
int main() {
	int n, i;
	scanf("%d%d", &n, &m );
	for (i = 1;i < n;i++) {
		int x, y;
		scanf("%d%d", &x, &y);
		v[x].push_back(y);
		v[y].push_back(x);
	}
	dfs(1,0);
	printf("%d", cnt);
	return 0;
}