예제 1.15 UVALive-3902 트리의 검색

컨베이어 도어
제목 대의: n대의 기계는 하나의 트리 네트워크로 연결되어 잎 노드는 클라이언트이고 다른 노드는 서버이다. 처음에는 한 대의 서버만 하나의 서비스를 제공했지만 k의 거리 내의 클라이언트만 덮어쓸 수 있다. 당신은 가능한 한 적은 서버가 이 서비스를 제공하여 모든 클라이언트를 덮어쓰도록 한다.
문제 풀이 사고방식: 우리는 이 뿌리 없는 나무를 뿌리 있는 나무로 전환한다. 그러면 서비스를 제공하는 서버는 뿌리 노드이고 k 깊이 이내의 잎 노드는 모두 덮어씌워지기 때문에 우리는 k 이하의 것을 찾으면 된다.가장 깊은 노드부터 찾으려면 덮어써야 합니다. k거리에서 떨어진 서버가 서비스를 제공하는 것이 가장 경제적입니다. 따라서 우리는 k급 조상을 찾으면 됩니다. 그러면 이 서버 주위의 k의 거리는 모두 덮어쓰고 한 번씩 훑어보면 됩니다.
AC 코드:

#include 
#include 
#include 
#include 

using namespace std;
const int maxn = 1000+5;

int n, s, k;
vector List[maxn], Nodes[maxn]; //List ， Nodes 

int fa[maxn];//  
bool covered[maxn];

void dfs_deep(int c, int f, int d) // ， ， 
{
	fa[c] = f;
	int cn = List[c].size();
	if(cn == 1 && d>k) Nodes[d].push_back(c);// 
	for(int i=0; ik; d--)// ， k ， k 
	{
		int cn = Nodes[d].size();
		for(int j=0; j