Live Archive 3902 Network 【持续更新】

3902 - Network
Asia - Seoul - 2007/2008
Consider a tree network with n nodes where the internal nodes correspond to servers and the terminal nodes
correspond to clients. The nodes are numbered from 1 to n . Among the servers, there is an original server S
which provides VOD (Video On Demand) service. To ensure the quality of service for the clients, the distance
from each client to the VOD server S should not exceed a certain value k . The distance from a node u to a
node v in the tree is defined to be the number of edges on the path from u to v . If there is a nonempty subset C
of clients such that the distance from each u in C to S is greater than k , then replicas of the VOD system have
to be placed in some servers so that the distance from each client to the nearest VOD server (the original VOD
system or its replica) is k or less.
Given a tree network, a server S which has VOD system, and a positive integer k , find the minimum number
of replicas necessary so that each client is within distance k from the nearest server which has the original
VOD system or its replica.
For example, consider the following tree network.
In the above tree, the set of clients is {1, 6, 7, 8, 9, 10, 11, 13}, the set of servers is {2, 3, 4, 5, 12, 14}, and the
original VOD server is located at node 12.
For k = 2 , the quality of service is not guaranteed with one VOD server at node 12 because the clients in {6,
7, 8, 9, 10} are away from VOD server at distance > k . Therefore, we need one or more replicas. When one
replica is placed at node 4, the distance from each client to the nearest server of {12, 4} is less than or equal to
2. The minimum number of the needed replicas is one for this example.
Input
Your program is to read the input from standard input. The input consists of T test cases. The number of test
cases (T ) is given in the first line of the input. The first line of each test case contains an integer n (3 n 1,
3902 - Network 1/2
000) which is the number of nodes of the tree network. The next line contains two integers s (1 s n) and k
(k 1) where s is the VOD server and k is the distance value for ensuring the quality of service. In the
following n - 1 lines, each line contains a pair of nodes which represent an edge of the tree network.
Output
Your program is to write to standard output. Print exactly one line for each test case. The line should contain
an integer that is the minimum number of the needed replicas.
Sample Input
2 14
12 2
1 2
2 3
3 4
4 5
5 6
7 5
8 5
4 9
10 3
2 12
12 14
13 14
14 11
14
3 4
1 2
2 3
3 4
4 5
5 6
7 5
8 5
4 9
10 3
2 12
12 14
13 14
14 11
Sample Output
1
0
Seoul 2007-2008
3902 - Network 2/2

题意：给你一颗树，每个叶子节点都是一个终端，起始是只有一个vod服务器（在节点s上），一个叶节点距离一个服务器节点的距离为不大于k时，此节点上的终端就能够得到很好的服务，反之则得不到。现在问你在原有的一个服务器的基础上最少再建立几个服务器站使得所有的终端都能够得到很好的服务。
分析：因为题目已经给出一个祖先了，那么我们可以以此祖先建立一颗树。考虑到一个叶子节点（终端）如果能够得到好的服务，那么离它的的距离为d（d

#include <cstdio>
#include <vector>
#include <cstring>
using namespace std;
const int maxn = 1e3+10;

vector<int > gr[maxn], node[maxn];//node用的很巧妙。
int fat[maxn], k, n;
bool cov[maxn];//标记节点是否

void dfs1(int u, int f, int d){//建立一个树
    fat[u] = f;
    int nc = gr[u].size();
    if(nc == 1&&d > k) node[d].push_back(u);
    for(int i = 0; i < nc; ++ i){
        int v = gr[u][i];
        if(v != f) dfs1(v, u, d+1);
    }
}

void dfs2(int u, int f, int d){//更新
    cov[u] = 1;
    for(int i = 0; i < gr[u].size(); ++ i){//在u处建立了一个站那么满足小于等于k的节点都标记一下。
        int v = gr[u][i];
        if(v != f&& d < k) dfs2(v, u, d+1);
    }
}

int solve(){
    memset(cov, 0, sizeof(cov));
    int ans = 0;
    for(int d = n-1; d > k; -- d){ //d就代表距离元祖先的距离，k+1~n-1（最大）
        for(int i = 0; i < node[d].size(); ++ i){
            int u = node[d][i];
            if(cov[u]) continue;
            int v = u;
            for(int j = 0; j < k; ++ j) v = fat[v];
            dfs2(v, -1, 0);
            ++ans;
        }
    }
    return ans;
}

int main(){
    int t;
    scanf("%d", &t);
    while(t --){
        scanf("%d", &n);
        int s;
        scanf("%d%d", &s, &k);
        for(int i = 0; i <= n; ++ i){
            gr[i].clear(); node[i].clear();
        }
        int a, b;
        for(int i = 0; i < n-1; ++ i){
            scanf("%d%d", &a, &b);
            gr[a].push_back(b);
            gr[b].push_back(a);
        } 
        dfs1(s, -1, 0);
        printf("%d\n", solve());
    }
    return 0;
}