题目链接：

题意：有n个城市，坐标1到n，n-1条边，长度都为1。然后有k个警局，下标pi。现在要求拆掉其中的一部分边，并且还要保证所有城市到警局距离小于等于d。一开始保证所有城市到金具距离小于等于d。输出删除的路径总数，以及删除的路径的id。

分析：将k个警局求入一个queue，然后bfs，vis数组标记是否到达某一个城市，初始话为0，如果是第一次到达（vis[i]=0），那么这条路是必须的，vis[i]=1,找到所有必须路径，剩下的就是可以删除的，完全不用考虑d。

AC代码：

1 #include
      
        2 using namespace std; 3  4 struct Node{ 5     int v; 6     int id; 7     Node(int _v,int _id){ 8         v=_v; 9         id=_id;10     }11 };12 int a[300005];13 vector
       
        g[300005];14 int vis[300005];15 int vis2[300005];16 queue
        
         q;17 int c[300005];18 int length[300005];19 int main() {20     ios_base::sync_with_stdio(0);21     cin.tie(0);22     int n,k,d;23     int u,v;24     memset(vis,0,sizeof(vis));25     memset(vis2,0,sizeof(vis2));26     cin>>n>>k>>d;27     for(int i=1;i<=k;i++){28         cin>>a[i];29         vis[a[i]]=1;30         q.push(a[i]);31     }32     sort(a+1,a+1+k);33     for(int i=1;i
         
          >u>>v;35         g[u].push_back(Node(v,i));36         g[v].push_back(Node(u,i));37     }38     int result=0;39     while(!q.empty()){40         int x=q.front();41         int sz=g[x].size();42         q.pop();43         for(int i=0;i