人生第一道图论题啊，有木有
题意：
有一个树状网络，有一个原始服务器s，它的服务范围是k
问至少再放多少台服务范围是k的服务器才能使网络中的每个节点都被覆盖掉
解法：
我们以原始服务器为根将其转化成一个有根树，则深度不超过k的节点都已经被原始服务器覆盖。
我们选择深度最大的节点u然后将它的k级祖先设为服务器，进行一次DFS，将所有距离它不超过k的节点覆盖。
表示：
图的表示在这里面是用邻接表来表示的，如果a、b两个节点相邻，则gr[a]中放入b，gr[b]中放入a
怎样才算转化为有根树了？那就是把每个节点的爸爸(father)算出来，记录在fa数组中
试想，如果深度大于k的节点都已被覆盖，那么其他非叶子节点也一顶被覆盖了
所以将深度大于k的节点放在nodes表中
//#define LOCAL
#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std; const int maxn = + ;
vector<int> gr[maxn], nodes[maxn];
int n, s, k, fa[maxn];
bool coverd[maxn]; void DFS(int u, int f, int d)
{//计算各个节点的祖先,放在fa数组中
fa[u] = f;
int nc = gr[u].size();
if(nc == && d > k)
nodes[d].push_back(u);
for(int i = ; i < nc; ++i)
{
int v = gr[u][i];
if(v != f)
DFS(v, u, d + );
}
} void DFS2(int u, int f, int d)
{
coverd[u] = true;
int nc = gr[u].size();
for(int i = ; i < nc; ++i)
{
int v = gr[u][i];
if(v != f && d < k)
DFS2(v, u, d + );
}
} int solve(void)
{
int ans = ;
memset(coverd, false, sizeof(coverd));
for(int d = n - ; d > k; --d)
for(int i = ; i < nodes[d].size(); ++i)
{
int u = nodes[d][i];
if(coverd[u]) continue; int v = u;
for(int i = ; i < k; ++i) //v是u的k级祖先
v = fa[v];
DFS2(v, -, );
++ans;
}
return ans;
} int main(void)
{
#ifdef LOCAL
freopen("3902in.txt", "r", stdin);
#endif int T;
scanf("%d", &T);
while(T--)
{
scanf("%d%d%d", &n, &s, &k);
for(int i = ; i <= n; ++i)
{
gr[i].clear();
nodes[i].clear();
}
for(int i = ; i < n - ; ++i)
{
int a, b;
scanf("%d%d", &a, &b);
gr[a].push_back(b);
gr[b].push_back(a);
}
DFS(s, -, );
printf("%d\n", solve());
}
return ;
}
代码君