本文共 1923 字，大约阅读时间需要 6 分钟。

题意

n个点有n-1条边相连，其中有k个特殊点，要求：
删去尽可能多的边使得剩余的点距特殊点的距离不超过d
输出删去的边数和index

分析

比赛的时候想不清楚，看了别人的题解
一道将1个联通块转化为k个树的题目，考虑上界，应该是k-1条边，这k-1条边是原图中连接树与树的边，那么我们操作如下：
1.将特殊点i染色为i，放入队列
2.做一次bfs，对每个点相邻的点染色并判断
3.遍历边，如果边的两点不同色，则输出边的index

trick

代码

#include <cstdio>#include <cstring>#include <cstdlib>#include <ctime>#include <cmath>#include <iostream>#include <algorithm>#include <string>#include <set>#include <map>#include <queue>#include <stack>#include <vector>#include <bitset>using namespace std;#define ll long long#define F(i,a,b) for(int i=a;i<=b;++i)#define R(i,a,b) for(int i=a;i<b;++i)#define mem(a,b) memset(a,b,sizeof(a))#define cpy(a,b) memcpy(a,b,sizeof(b))#pragma comment(linker, "/STACK:102400000,102400000")inline void read(int &x){x=0; char ch=getchar();while(ch<'0') ch=getchar();while(ch>='0'){x=x*10+ch-48; ch=getchar();}}int n,k,d,u,v;vector<int>vec[300300];vector<pair<int,int> >edg;int f[300300],color[300300],dis[300300];int cnt;queue<int>q;void bfs(){    while(!q.empty())    {        int u=q.front();q.pop();        if(dis[u]==d) continue;        R(i,0,vec[u].size())        {            int v=vec[u][i];            if(!color[v])            {                color[v]=color[u];                dis[v]=dis[u]+1;                q.push(v);            }        }    }}int main(){    scanf("%d %d %d",&n,&k,&d);    F(i,1,k)    {        int x;        scanf("%d",&x);        f[x]=1;    }    F(i,1,n-1)    {        scanf("%d %d",&u,&v);        edg.push_back(make_pair(u,v));        vec[u].push_back(v);        vec[v].push_back(u);    }    cnt=0;    F(i,1,n)if(f[i])    {        q.push(i);        color[i]=i;        cnt++;    }    bfs();    printf("%d\n",cnt-1);    int now=0;    //F(i,1,n) printf("color[%d]=%d\n",i,color[i]);    R(i,0,n-1)    {        int u=edg[i].first,v=edg[i].second;        if(color[u]!=color[v])        {            ++now;            printf("%d%c",i+1,(now==(k-1))?'\n':' ');        }    }    return 0;}