【题解】LA 3902【Network】

分析

先将无根树转换成有根树,这题都有一个天然根节点(原始VOD服务器),对于那些已经满足条件的客户端来说,他们就是不存在的,然后这里有一个实现方法:每放一个服务器,就进行一次DFS,覆盖与它距离不超过$k$的所有结点。

代码

#include<cstdio>
#include<cstring>
#include<vector>
#include<algorithm>
using std::vector;
const int MAXN = 1000 + 6;
vector<int> gr[MAXN],nodes[MAXN];
int n,s,k,fa[MAXN];
bool covered[MAXN];

void dfs(int u,int f,int d){
    fa[u] = f;
    int nc = gr[u].size();
    if(nc == 1 && d > k) nodes[d].push_back(u);
    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--){
        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;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\n",solve());
    }

    return 0;
}