예제 1.15 네트워크 UVALive 3902

1. 제목 설명: 클릭 하여 링크 열기
2. 문제 풀이 방향: 본 문 제 는 가능 한 한 적은 서버 를 설치 하여 모든 클 라 이언 트 가 가장 가 까 운 서버 까지 의 거리 가 k 를 초과 하지 않도록 해 야 합 니 다.서버 가 설치 되 어 있 기 때문에 뿌리 점 으로 삼 아 뿌리 없 는 나 무 를 뿌리 있 는 나무 로 바 꾼 다음 에 가장 깊 은 잎 을 고려 하면 이 잎 결점 의 가장 좋 은 서버 의 배치 위 치 는 k 급 조상 임 을 증명 하기 어렵 지 않다.이 문제 의 알고리즘 은 가장 깊 은 잎 부터 매 거 하고 k 급 조상 에 게 서버 를 설치 하 며 서버 가 덮 을 수 있 는 모든 결점 을 표시 합 니 다. 그러면 모든 잎 이 덮 일 때 서버 수량 이 가장 적 습 니 다.k + 1 층 까지 매 거 진 잎 만 있 으 면 멈 출 수 있 습 니 다. k 보다 작은 잎 은 이미 뿌리 결점 으로 덮 여 있 기 때 문 입 니 다.
이 문 제 는 깊이 가 k 인 모든 잎 을 쉽게 찾기 위해 우 리 는 전환 과정 에서 잎의 결점 을 nodes 배열 에 넣 었 다. 이렇게 nodes [k] 는 바로 k 층 의 모든 잎 을 나 타 냈 다.
3. 코드:

#define _CRT_SECURE_NO_WARNINGS 
#include<iostream>
#include<algorithm>
#include<string>
#include<sstream>
#include<set>
#include<vector>
#include<stack>
#include<map>
#include<queue>
#include<deque>
#include<cstdlib>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<ctime>
#include<functional>
using namespace std;

#define N 1000+10
vector<int>gr[N], nodes[N];
int n, s, k, fa[N];
bool covered[N];
void dfs(int u, int f, int d)//       ，  fa  ，           nodes  
{
	fa[u] = f;
	int nc = gr[u].size();
	if (nc == 1 && d > k)nodes[d].push_back(u);//nc==1       
	for (int i = 0; i < nc; i++)
	{
		int v = gr[u][i];
		if (v != f)dfs(v, u, d + 1);
	}
}
void dfs2(int u, int f, int d)
{
	covered[u] = true;
	int nc = gr[u].size();
	for (int i = 0; i < nc; i++)
	{
		int v = gr[u][i];
		if (v != f&&d < k)dfs2(v, u, d + 1);
	}
}
int solve()
{
	int ans = 0;
	memset(covered, 0, sizeof(covered));
	for (int d = n - 1; d>k; d--)//     n-1，          
	for (int i = 0; i < nodes[d].size();i++)
	{
		int u = nodes[d][i];
		if (covered[u])continue;
		int v = u;
		for (int j = 0; j < k; j++)v = fa[v];// u k   v
		dfs2(v, -1, 0);//   v    ，        
		ans++;
	}
	return ans;
}
int main()
{
	//freopen("t.txt", "r", stdin);
	int T;
	scanf("%d", &T);
	while (T--)
	{
		scanf("%d%d%d", &n, &s, &k);
		for (int i = 1; i <= n; i++)
		{
			gr[i].clear();
			nodes[i].clear();
		}
		for (int i = 0; i < n - 1; i++)
		{
			int a, b;
			scanf("%d%d", &a, &b);
			gr[a].push_back(b);
			gr[b].push_back(a);
		}
		dfs(s, -1, 0);
		printf("%d
", solve());
	}
	return 0;
}