网络 network,Seoul 2007 LA3902 解题感想

一道关于 DFS 的题目, 关键在于距离 K, 将服务器的节点作为根节点进行DFS

#include <cstdio>
#include <iostream>
#include <vector>
using namespace std;

const int maxn = 1000 + 10;
vector<int> tree[maxn], nodes[maxn];
int fa[maxn];
int s, k, n;
bool covered[maxn];
void dfs(int child, int father, int depth){
	fa[child] = father;
	int newnode = tree[child].size();
	if (newnode&&depth>k)
	{
		nodes[depth].push_back(child);
	}
	for (int i = 0; i < newnode;i++)
	{
		int newchild = tree[child][newnode];
		if (newchild != father) dfs(newchild, child, depth + 1);
	}
}


void dfs2(int serve, int father, int depth){
	covered[serve] = true;
	int nsurround = tree[serve].size();
	for (int i = 0; i < nsurround; i++){
		int v = tree[serve][i];
		if (v != father&&depth < k) dfs2(v, serve, depth + 1);
	}
}

int solve(){
	int ans = 0;
	memset(covered, 0, sizeof(covered));
	for (int d = n - 1; d > k;d--)
	{
		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];
			dfs2(v, -1, 0);
			ans++;
		}
	}
	return ans;
}



int main(){
	int T;
	cin >> T;
	while (T--){
		cin >> n >> s >> k;
		for (int i = 0; i <= n;i++)
		{
			tree[i].clear();
			nodes[i].clear();
			
		}
		for (int i = 0; i < n-1;i++)
		{
			int a, b;
			cin >> a >> b;
			tree[a].push_back(b);
			tree[b].push_back(a);
		}
		dfs(s, -1, 0);
		cout << solve();


	}
	return 0;
}