Codeforces 796D

发表于 |

题目

给一颗树，$N$个点，$N-1$条边。有$K$个警察局，第$i$个警察局在点$p_i$上。

性质$P$定义为：对任意点$v$，存在警察局$u$，使得$dist(u,v)\leq D$ 。

初始的图满足性质$P$。

问：最多删除哪些边使得图仍然满足性质$P$。

数据范围

$2\leq N \leq 3\times 10^5\quad 1 \leq K \leq 3 \times 10^5 \quad 0\leq D \leq N-1$

做法

先考虑最多能删除多少边。在树上，每删除一条边，就多一个连通块。为了满足性质$P$，显然最多只能有$K_{real}$个连通块。其中，$K_{real}$为其上有警察局的节点的个数。这点容易反证得出。由此，我们得出了删除的边数的一个上界是$K_{real}−1$ 。

现在考虑如何删。由于初始图满足性质$P$，所以每个点到距其最近的警察局的距离$\leq D$。于是，我们只要保证每个点能够到达距其最近的警察局即可，其余的边都删掉。这样，我们便将树分成了$K_{real}$个连通块，也即删去了$K_{real}-1$条边。

所以，最多删去$K_{real}-1$条边，删除方法如上所述，可用$BFS$实现。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
const int MAX_N = 3e5 + 5;
int N, K, D;
vector<int> G[MAX_N];
bool p[MAX_N];
map<pii, int> edge_id;
bool vis[MAX_N];
bool edge_del[MAX_N];
int d[MAX_N];
void AddEdge(int a, int b)
{
  G[a].push_back(b);
  G[b].push_back(a);
}
void Bfs()
{
  queue<int> que;
  for (int i = 0; i < N; ++i) {
    if (p[i]) {
      que.push(i);
      vis[i] = 1;
      d[i] = 0;
    }
  }
  while (!que.empty()) {
    int v = que.front(); que.pop();
    for (int i = 0; i < (int)G[v].size(); ++i) {
      int u = G[v][i];
      if (!vis[u]) {
        que.push(u);
        vis[u] = 1;
        d[u] = d[v] + 1;
      } else {
        if (d[u] >= d[v]) {
          int v1 = min(u, v), v2 = max(u, v);
          edge_del[edge_id[pii(v1, v2)]] = 1;
        }
      }
    }
  }
}
int main()
{
  cin >> N >> K >> D;
  for (int i = 0; i < K; ++i) {
    int tmp; scanf("%d", &tmp);
    p[--tmp] = 1;
  }
  for (int i = 1; i < N; ++i) {
    int a, b; scanf("%d%d", &a, &b); --a; --b;
    AddEdge(a, b);
    if (a > b) swap(a, b);
    edge_id[pii(a, b)] = i;
  }
  Bfs();
  int edge_del_num = 0;
  for (int i = 1; i < N; ++i) {
    if (edge_del[i]) ++edge_del_num;
  }
  printf("%d\n", edge_del_num);
  for (int i = 1; i < N; ++i) {
    if (edge_del[i]) printf("%d%c", i, --edge_del_num ? ' ' : '\n');
  }
  return 0;
}

注意

  1. 对删除的边计数的时候，注意去重。

  2. 开始我的做法不是对有警察局的点一起$BFS$，而是对这些点一个一个$BFS$。但是这样会造成删边之后有些点不能到达警察局。不满足性质$P$。

    比如下图，$1$和$5$有警察局，$D=2$。如果从$1$开始$BFS$，那么会造成搜不到$4$的情况。img