首页 > 试题广场 > CodeForces 337D Book of Evil
[编程题]CodeForces 337D Book of Evil

Paladin Manao caught the trail of the ancient Book of Evil in a swampy area. This area contains n settlements numbered from 1 to n . Moving through the swamp is very difficult, so people tramped exactly n - 1 paths. Each of these paths connects some pair of settlements and is bidirectional. Moreover, it is possible to reach any settlement from any other one by traversing one or several paths.

The distance between two settlements is the minimum number of paths that have to be crossed to get from one settlement to the other one. Manao knows that the Book of Evil has got a damage range d . This means that if the Book of Evil is located in some settlement, its damage (for example, emergence of ghosts and werewolves) affects other settlements at distance d or less from the settlement where the Book resides.

Manao has heard of m settlements affected by the Book of Evil. Their numbers are p 1, p 2, ..., p m . Note that the Book may be affecting other settlements as well, but this has not been detected yet. Manao wants to determine which settlements may contain the Book. Help him with this difficult task.


输入描述:

The first line contains three space-separated integers n, m and d (1 ≤ m ≤ n ≤ 100000; 0 ≤ d ≤ n - 1). The second line contains m distinct space-separated integers p1, p2, ..., pm (1 ≤ pi ≤ n). Then n - 1 lines follow, each line describes a path made in the area. A path is described by a pair of space-separated integers ai and bi representing the ends of this path.



输出描述:

Print a single number — the number of settlements that may contain the Book of Evil. It is possible that Manao received some controversial information and there is no settlement that may contain the Book. In such case, print 0.

示例1

输入

6 2 3
1 2
1 5
2 3
3 4
4 5
5 6

输出

3

备注:

Sample 1. The damage range of the Book of Evil equals 3 and its effects have been noticed in settlements 1 and 2. Thus, it can be in settlements 3, 4 or 5.

1个回答

添加回答
先找出相距最远的2个幽灵节点(由于每条边的距离为1,所以可以用bfs,不然就只能用Dijkstra),然后各自以幽灵节点自身为中心,向外bfs C层(C <= d),把这些层的节点都放入一个集合,最后两个集合求交就是答案了。
由于是树型结构,所以只要包含了相距最远的2个幽灵节点就包含了所有幽灵节点,可以用反证法证明。
#include <bits/stdc++.h>
using namespace std;

#define rep(i,n) for (int i = 0; i < (n); ++i)
#define For(i,s,t) for (int i = (s); i <= (t); ++i)
#define rFor(i,t,s) for (int i = (t); i >= (s); --i)
#define foreach(i,c) for (__typeof(c.begin()) i = c.begin(); i != c.end(); ++i)
#define rforeach(i,c) for (__typeof(c.rbegin()) i = c.rbegin(); i != c.rend(); ++i)

#define pr(x) cout << #x << " = " << x << "  "
#define prln(x) cout << #x << " = " << x << endl

#define LOWBIT(x) ((x)&(-x))

#define ALL(x) x.begin(),x.end()
#define INS(x) inserter(x,x.begin())

#define ms0(a) memset(a,0,sizeof(a))
#define msI(a) memset(a,inf,sizeof(a))
#define msM(a) memset(a,-1,sizeof(a))

#define pii pair<int,int> 
#define piii pair<pair<int,int>,int> 
#define mp make_pair
#define pb push_back
#define fi first
#define se second

inline int gc(){
    static const int BUF = 1e7;
    static char buf[BUF], *bg = buf + BUF, *ed = bg;
    
    if(bg == ed) fread(bg = buf, 1, BUF, stdin);
    return *bg++;
} 

inline int ri(){
    int x = 0, f = 1, c = gc();
    for(; c<48||c>57; f = c=='-'?-1:f, c=gc());
    for(; c>47&&c<58; x = x*10 + c - 48, c=gc());
    return x*f;
}

typedef long long LL;
typedef unsigned long long uLL;
const int inf = 1e9 + 9;
const LL mod = 1e9 + 7;
const int maxN = 1e5 + 7;

struct Node{
    vector< int > next;
};

int n, m, d, ans;
int vis[maxN];
int ghost[maxN]; // 记录是否是幽灵 
int state[maxN]; // 标记是否可能存在书,值为2的时候才存在 
Node nodes[maxN];
queue< int > Q;

int g_1, g_2; // 最远幽灵点对 

// 返回与幽灵节点x距离最远的幽灵节点的幽灵节点序号 
int bfs_1(int x) {
    int dist = 1;
    int cnt = m - 1, cnt_1 = 1;
    if(cnt == 0) return x;
    while(!Q.empty()) Q.pop();
    ms0(vis);
    vis[x] = 1; 
    Q.push(x);
    
    while(!Q.empty()) {
        --cnt_1;
        if(dist > 2 * d) return -1;
        int tmp = Q.front();
        Q.pop();
        
        foreach(i, nodes[tmp].next) {
            if(vis[*i]) continue;
            vis[*i] = 1;
            if(ghost[*i] == 1) {
                --cnt;
                if(cnt == 0) return *i;
            }
            Q.push(*i);
        }
        if(cnt_1 == 0) {
            ++dist;
            cnt_1 = Q.size();
        }
    }
}

// 以幽灵节点x为中心,向外bfs,记录所有与x距离小于等于d的节点,自身节点也算 
void bfs_2(int x) {
    int dist = 1, cnt_1 = 1;
    while(!Q.empty()) Q.pop();
    ms0(vis);
    vis[x] = 1; 
    Q.push(x);
    ++state[x];
    
    while(!Q.empty()) {
        --cnt_1;
        if(dist > d) return;
        int tmp = Q.front();
        Q.pop();
        
        foreach(i, nodes[tmp].next) {
            if(vis[*i]) continue;
            vis[*i] = 1;
            ++state[*i];
            Q.push(*i);
        }
        if(cnt_1 == 0) {
            ++dist;
            cnt_1 = Q.size();
        }
    }
}

int main(){
    cin >> n >> m >> d;
    For(i, 1, m) {
        cin >> g_1;
        ghost[g_1] = 1;
    }
    
    For(i, 1, n-1) {
        int x, y;
        cin >> x >> y;
        nodes[x].next.push_back(y);
        nodes[y].next.push_back(x);
    }
    
    g_2 = bfs_1(g_1); 
    g_1 = bfs_1(g_2); 
    
    if(g_1 != -1 && g_2 != -1) {
        bfs_2(g_1);
        bfs_2(g_2);
        
        For(i, 1, n) if(state[i] == 2) ++ans;
    }
    
    cout << ans << endl;
    return 0;
}

/*
25 7 8
2 6 9 13 20 17 23
1 2
1 3
1 4
2 5
5 8
5 9
8 15
9 16
3 6
6 10
6 11
6 12
6 13
11 17
17 22
17 23
12 18
4 7
7 14
14 19
14 20
20 24
20 25
14 21

ans: 16
*/

发表于 2019-04-16 11:58:04 回复(0)

扫一扫,把题目装进口袋

牛客网,程序员必备求职神器

扫描二维码,进入QQ群

扫描二维码,关注牛客网公众号