hdu 4707 Pet 2013年ICPC热身赛A题 dfs水题

题意：linji的仓鼠丢了，他要找回仓鼠，他在房间0放了一块奶酪，按照抓鼠手册所说，这块奶酪可以吸引距离它D的仓鼠，但是仓鼠还是没有出现，现在给出一张关系图，表示各个房间的关系，相邻房间距离为1，而且图中没有回路，每个房间都是联通的，求仓鼠可能出现的房间的数量。

很容易的dfs，50000个房间数据量比较大，用数组难以保存，于是用vector储存关系表。遍历过去，遍历过几个房间，那剩下的就是仓鼠可能出现的房间数了。

代码：

/*
*  Author:      illuz <iilluzen[at]gmail.com>
*  Blog:        http://blog.****.net/hcbbt
*  File:        2.cpp
*  Create Date: 2013-09-08 13:52:18
*  Descripton:  dfs
*/

#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;
#define rep(i, n) for (int i = 0; i < (n); i++)
#define mc(a) memset(a, 0, sizeof(a))

const int MAXN = 1e5 + 1;
vector<int> v[MAXN];
int n, d, cnt;
bool vis[MAXN];

void dfs(int p, int e) {
	if (e > d) return;
	vis[p] = 1;
	cnt++;
	int len = v[p].size();
	rep(i, len)
		if (!vis[v[p][i]])
			dfs(v[p][i], e + 1);
}

int main() {
	int t, a, b;
	scanf("%d", &t);

	while (t--) {
		rep(i, n) v[i].clear();
		mc(vis);
		cnt = 0;
		scanf("%d%d", &n, &d);
		rep(i, n - 1) {
		   	scanf("%d%d", &a, &b);
			v[a].push_back(b);
			v[b].push_back(a);
		}
		dfs(0, 0);
		printf("%d\n", n - cnt);
	}
	return 0;
}