原题链接
题意：
给定一棵树，树上有一些点是警察局，要求所有点到最近的警察局的距离不大于d，求最多能删几条边。
思路：
光看简略版题意可能会漏掉重要信息，原题中有这样一句话：
from each city it must be possible to reach a police station by traveling at most d kilometers along the roads.
也就是说原图就是满足条件的。
因为要求最近的警察局，很容易想到bfs，我们对所有的警察局进行标号，并且从所有的警察局出发进行bfs,这样如果某条边的两个端点的颜色不一样，就说明这条边可以删去，并且删去后端点依旧可以到达另一个警察局。
由于bfs的性质和原图的条件，这样删除是合法的。
代码：
#pragma GCC optimize(2) #include<bits/stdc++.h> using namespace std; typedef long long ll; typedef unsigned long long ull; typedef pair<ll,ll>PLL; typedef pair<int,int>PII; typedef pair<double,double>PDD; #define I_int ll inline ll read() { ll x=0,f=1; char ch=getchar(); while(ch<'0'||ch>'9') { if(ch=='-')f=-1; ch=getchar(); } while(ch>='0'&&ch<='9') { x=x*10+ch-'0'; ch=getchar(); } return x*f; } #define read read() #define closeSync ios::sync_with_stdio(0);cin.tie(0);cout.tie(0) #define multiCase int T;cin>>T;for(int t=1;t<=T;t++) #define rep(i,a,b) for(int i=(a);i<=(b);i++) #define repp(i,a,b) for(int i=(a);i<(b);i++) #define per(i,a,b) for(int i=(a);i>=(b);i--) #define perr(i,a,b) for(int i=(a);i>(b);i--) ll ksm(ll a,ll b,ll p) { ll res=1; while(b) { if(b&1)res=res*a%p; a=a*a%p; b>>=1; } return res; } #define PI acos(-1) #define x first #define y second const int maxn=1e6+7,inf=0x3f3f3f3f; int n,k,d,idx; vector<int>g[maxn]; int vis[maxn]; PII p[maxn]; queue<PII>q; void bfs(){ while(!q.empty()){ PII t=q.front();q.pop(); for(int v:g[t.x]){ if(!vis[v]){ vis[v]=t.y; q.push({v,vis[v]}); } } } } int main() { n=read,k=read,d=read; for(int i=1;i<=k;i++){ int x=read; if(!vis[x]) vis[x]=++idx; q.push({x,vis[x]}); } for(int i=1;i<n;i++){ int u=read,v=read; g[u].push_back(v); g[v].push_back(u); p[i]={u,v}; } bfs(); vector<int>v; for(int i=1;i<n;i++) if(vis[p[i].x]!=vis[p[i].y]){ v.push_back(i); } cout<<v.size()<<endl; for(int t:v) cout<<t<<" "; return 0; }
