CF796D Police Stations

Floating_Trees · 2025-06-28 14:03:49 · 题解

思路

贪心，bfs。

题目已经保证任意一个点到警局的距离小于等于 d，所以这个 d 是没用的。

我们从每一个警局开始 bfs，找到离每一个点最近的警局，并记录，也就是染色，如果两个点的颜色不同，说明这两个点所需要的警局不同，那么这两个点之间的边就没有用处，就可以删掉。

需要注意给出的警局会有重复，所以如果手写队列要开两倍空间或者先去重。

代码

#include <bits/stdc++.h>

using namespace std;

const int N = 3e5 + 10;
int n, m, d, c[N], vis[N], uu[N], vv[N], ok[N];
vector<int> E[N];
queue<int> q;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);

    cin >> n >> m >> d;
    for (int i = 1, x;i <= m;i++)
        cin >> x, q.push(x), c[x] = i, vis[x] = 1;
    for (int i = 1;i < n;i++)
        cin >> uu[i] >> vv[i], E[uu[i]].emplace_back(vv[i]), E[vv[i]].emplace_back(uu[i]);
    while (!q.empty())
    {
        int u = q.front(); q.pop();
        for (auto v : E[u])
            if (!vis[v])
                c[v] = c[u], q.push(v), vis[v] = 1;
    }
    int cnt = 0;
    for (int i = 1;i < n;i++)
        if (c[uu[i]] != c[vv[i]])
            cnt++, ok[i] = 1;
    cout << cnt << "\n";
    for (int i = 1;i < n;i++)
        if (ok[i])
            cout << i << " ";

    return 0;
}