CF796D解题报告

tang2hao4zhe2 · 2025-01-01 18:46:16 · 个人记录

洛谷

Solution

从每个警局往外bfs，遍历到距离不超过d的点，遍历到的边是不能删的

Code

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=3e5+5;
bool ispolice[N];
struct edge{
    int to,id;
};
vector<edge> G[N];
void addedge(int u,int v,int id){
    G[u].push_back((edge){v,id});
}
queue<pair<int,int> > q;
bool vis[N],have[N];
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);

    int n,k,d;cin>>n>>k>>d;
    for(int i=1;i<=k;i++){
        int t;cin>>t;
        ispolice[t]=true;
    }
    for(int i=1;i<=n-1;i++){
        int u,v;cin>>u>>v;
        addedge(u,v,i);
        addedge(v,u,i);
    }
    for(int i=1;i<=n;i++) if(ispolice[i]){
        q.push(make_pair(i,0));
        vis[i]=true;
    }
    while(!q.empty()){
        auto t=q.front();q.pop();
        int u=t.first,dep=t.second;
        for(edge e:G[u]){
            int v=e.to,id=e.id;
            if(vis[v]||dep+1>d) continue;
            have[id]=true;
            vis[v]=true;
            q.push(make_pair(v,dep+1));
        }
    }
    vector<int> ans;
    for(int i=1;i<=n-1;i++) if(!have[i]) ans.push_back(i);
    cout<<ans.size()<<endl;
    for(int i:ans) cout<<i<<' ';
    cout<<endl;
    return 0;
}