$\color{deeppink}link$

给定一个基环树，叫你求最少要割几边才能有 $k$ 个点被隔离。

贪心。

对于每一个基环树，我们讨论以下几种情况：

• 中心点在环外：

显然只能割断中心点周围的边。

• 中心点在环上：

如果把中心点的子树抛开，只有两种情况。

割一条边：若割环上的，那没有用，那就割其他点的儿子。此时最大隔离数为其他点中某个儿子的子树节点数的最大数。

割两条边：就割中心点两边的边，把环上其他点隔离，共隔离 $sum_i-siz_{ro_i}$（$sum_i$ 是基环树上节点总数，$ro_i$ 是基环树的根）。

显然割大于两条边没用。中心点的子树与上面的情况一起单独处理。

现在对于中心点在环上的树，我们定义它的权值 $val_{i,1/2}$ 表示割 1/2 条边的隔离数。

另外定义 $a$ 为割中心点周围的边的隔离数。以上的所有跑次拓扑及几次 dfs 即可（基环树基操）。

现在可以推出以下 6 种选择：

• 选一个没割过的树 $i$，割掉一条边，贡献是 $val_{i,1}$。

• 选一个割过一条边的树 $i$，再割掉一条边，贡献是 $val_{i,2}-val_{i,1}$。

• 选 $a$ 中的一条边割掉，贡献是 $a_i$。

• 选一个已经割掉一条边的树 $j$ 以及没割边的树 $i$，把割 $j$ 的边反悔掉，再割 $i$ 两条边，贡献是 $val_{i,2}-val_{j,1}$。

• 选一个已经割掉两条边的树 $j$ 以及没割边的树 $i$，把割 $j$ 的第二条边反悔掉，再割 $i$ 两条边，贡献是 $val_{i,2}-val_{j,2}+val_{j,1}$。

• 选一个被割过的 $a_j$，把其反悔掉，再割两条树 $i$ 的边，贡献是 $val_{i,2}-a_j$。

最后就是模拟以上过程，把贡献加起来，当贡献大于 $k$ 时退出即可。

还有就是注意把元素及时加到堆里，以及只有中心点周围可以的割的边。

简化版？
别问我为什么蓝题会变紫题的简化。

$code$

#include<bits/stdc++.h>
using namespace std;
const int N=2e6+50,inf=1919810;

struct node
{
	int u,v,nxt;
}e[N];

struct wty
{
	int id,val;
	
	friend bool operator<(wty a,wty b)
	{
		return a.val<b.val;
	}
};

int out[N],cnt,head[N],siz[N],vis[N],ans,ro[N],Mi[N],tot,n,k,val[N][3];
queue<int>q;priority_queue<wty>q1,q2,q3,q4,q5,q6,q7;
/*
未选的,a[i]
未选的,b[i]
已选一次的,b[i]-a[i]
已选一次的,-a[i]
已选二次的,a[i]-b[i]
*/

void add(int u,int v)
{
	e[++cnt]=(node){u,v,head[u]};head[u]=cnt;++out[u];
	e[++cnt]=(node){v,u,head[v]};head[v]=cnt;++out[v];
}

void tp()
{
	while(!q.empty())
	{
		int x=q.front();q.pop();
		for(int i=head[x];i;i=e[i].nxt)
		{
			int v=e[i].v;
			--out[v];
			if(out[v]==1)q.push(v);
		}
	}
}

void dfs(int x,int fa)
{
	Mi[x]=x;siz[x]=1;
	for(int i=head[x];i;i=e[i].nxt)
	{
		int v=e[i].v;
		if(v==fa||out[v]>=2)continue;
		dfs(v,x);Mi[x]=min(Mi[v],Mi[x]);
		siz[x]+=siz[v];
	}
}

void dfs2(int x)
{
	ro[tot]=min(ro[tot],Mi[x]);vis[x]=1;
	val[tot][2]+=siz[x];
	for(int i=head[x];i;i=e[i].nxt)
	{
		int v=e[i].v;
		if(out[v]>=2)
		{
			if(!vis[v])
			dfs2(v);
		}
	}
}

void dfs3(int x,int no)
{
	vis[x]=1;
	for(int i=head[x];i;i=e[i].nxt)
	{
		int v=e[i].v;
		if(x!=ro[no]&&out[v]<2)val[no][1]=max(val[no][1],siz[v]);
		if(out[v]>=2)
		{
			if(!vis[v])
			dfs3(v,no);
		}
	}
}

void pre()
{
	while(q1.size()&&vis[q1.top().id]!=0)q1.pop();
	while(q2.size()&&vis[q2.top().id]!=0)q2.pop();
	while(q3.size()&&vis[q3.top().id]!=1)q3.pop();
	while(q4.size()&&vis[q4.top().id]!=1)q4.pop();
	while(q5.size()&&vis[q5.top().id]!=2)q5.pop();
}

main()
{
	std::ios::sync_with_stdio(false);
    std::cin.tie(0);
	memset(ro,127,sizeof ro);
	cin>>n>>k;
	for(int i=1;i<=n;i++)
	{
		int u,v;
		cin>>u>>v;
		add(u,v);
	}
	for(int i=1;i<=n;i++)if(out[i]==1)q.push(i);
	tp();for(int i=1;i<=n;i++)if(out[i]>=2)dfs(i,0);
	for(int i=1;i<=n;i++)if(out[i]>=2&&vis[i]==0)++tot,dfs2(i);
	memset(vis,0,sizeof vis);
	for(int i=1;i<=tot;i++)
	{
		int x=ro[i];
		for(int j=head[x];j;j=e[j].nxt)
		{
			int v=e[j].v;
			if(siz[v]>siz[x]||out[v]>=2)continue;
			q6.push((wty){i,siz[v]});
		}
		if(out[ro[i]]<2)//root 非环
		{
			q6.push((wty){i,val[i][2]-siz[x]});
			continue;
		}
		dfs3(ro[i],i);val[i][2]-=siz[ro[i]];
		q1.push((wty){i,val[i][1]});
		q2.push((wty){i,val[i][2]});
	}
	memset(vis,0,sizeof vis);
	while(1)
	{
		if(k<=0)break;
		++ans;
		int val1,val2,val3,val4,val5,val6;
		val1=val2=val3=val4=val5=val6=-inf;
		pre();
		if(!q1.empty())val1=q1.top().val;
		if(!q3.empty())val2=q3.top().val;
		if(!q2.empty()&&!q4.empty())val3=q2.top().val+q4.top().val;
		if(!q2.empty()&&!q5.empty())val4=q2.top().val+q5.top().val;
		if(!q6.empty())val5=q6.top().val;
		if(!q2.empty()&&!q7.empty())val6=q7.top().val+q2.top().val;
		if(val6>=val1&&val6>=val2&&val6>=val3&&val6>=val4&&val6>=val5)
		{
			k-=val6;
			q6.push((wty){q7.top().id,-q7.top().val});
			q7.pop();int x=q2.top().id;q2.pop();
			vis[x]=2;
			q5.push((wty){x,val[x][1]-val[x][2]});
			continue;
		}
		if(val5>val1&&val5>val2&&val5>val3&&val5>val4)
		{
			k-=val5;
			q7.push((wty){q6.top().id,-q6.top().val});q6.pop();
			continue;
		}
		if(val1>=val2&&val1>=val3&&val1>=val4)
		{
			k-=val1;int x=q1.top().id;q1.pop();
			vis[x]=1;
			q3.push((wty){x,val[x][2]-val[x][1]});
			q4.push((wty){x,-val[x][1]});
			continue;
		}
		if(val2>=val1&&val2>=val3&&val2>=val4)
		{
			k-=val2;int x=q3.top().id;q3.pop();
			vis[x]=2;
			q5.push((wty){x,val[x][1]-val[x][2]});
			continue;
		}
		if(val3>=val4)
		{
			k-=val3;int x=q2.top().id,y=q4.top().id;q2.pop(),q4.pop();
			vis[x]=2,vis[y]=0;
			q5.push((wty){x,val[x][1]-val[x][2]});
			q1.push((wty){y,val[y][1]});
			q2.push((wty){y,val[y][2]});
			continue;
		}
		k-=val4;int x=q2.top().id,y=q5.top().id;q2.pop(),q5.pop();
		vis[x]=2;vis[y]=1;
		q5.push((wty){x,val[x][1]-val[x][2]});
		q3.push((wty){y,val[y][2]-val[y][1]});
		q4.push((wty){y,-val[y][1]});
	}
	cout<<ans;
}

话说这首歌还挺好听