UVA - 1267 Network

题意:n台の机械は1つの木の状のネットワークにつながって、その中の叶のノードはクライアントで、その他のノードはサーバーで、今1台のサーバーはサービスを提供して、あなたの任务はいくつかのその他のサーバーでインストールしてそれにサービスを提供させて、1台のクライアントから最近のサーバーまでの距离はKを超えないで、インストールの最低のサーバーはいくらです
考え方:無根樹を有根樹に変えることは問題を解くのに役立ち、本題にはすでに天然の根ノードがあり、条件を満たすノードは直接存在しないと見なせばよい.一般に、リーフノードuについては、uのkレベルの祖先を選択してサーバをインストールし、サーバを1回置くたびにDFSを行い、Kを超えないすべてのノードタグを選択します.
この問題の最適な点は、nodesテーブルを使用して「深さでソート」する操作を避けることです.

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
const int MAXN = 1010;

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
",solve());
    }
    return 0;
}