自动搬运

查看原文

来自洛谷，原作者为

	Miraik 看啊那只蝴蝶 飞过时间 落在心间

搬运于2025-08-24 22:24:58，当前版本为作者最后更新于2022-11-18 08:28:49，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

对于每棵内向基环树，我们首先不管环，把其他节点解决掉。

考虑一种贪心的想法：连叶子节点，然后将当前距离 $\le k$ 的点删掉，再继续连叶子节点，直至环外所有点都被删去。正确性比较显然，因为这样你自下而上拓展的速度最快。DFS 或 拓扑排序 都可以解决。

考虑环怎么办。刚才处理完了环外的点，因此现在 $1$ 号节点到环上每点的距离是已知的。不妨先利用每个点到 $1$ 号节点的距离在环上差分一下，可以求出那些与 $1$ 号节点距离大于 $k$ 的点，看作关键点。然后暴力扫描，枚举其中一个关键点作为起点，在环上不停向后覆盖，每覆盖一次都直接将指针向后移 $k$ 步，这样我们单次扫描的复杂度就是 $O(\frac{len}{k})$ 的了（$len$ 为环长）。

注意到我们只需要枚举前 $k$ 个关键点（至多前 $k$ 个为一段，那么以它们作为起点的情况已经包含了所有形态），因此对每个环我们这样做的复杂度就是 $O(\frac{len}{k} \times k)=O(len)$。

总时间复杂度 $O(n)$。有一点点细节，比如说 $1$ 号点在环外计算时的特殊处理。

void tarjan(int u){ // tarjan 找环
	dfn[u]=low[u]=(++idx);
	stc[++top]=u; ins[u]=1;
	int v=to[u];
	if(!dfn[v]){
		tarjan(v);
		low[u]=min(low[u],low[v]);
	}
	else if(ins[v]) low[u]=min(low[u],dfn[v]);
	if(low[u]==dfn[u]){
		if(stc[top]==u){
			ins[stc[top]]=0; top--;
			return;
		}
		t++;
		while(stc[top]^u)
			g[t].emplace_back(stc[top]),ins[stc[top]]=0,top--;
		g[t].emplace_back(stc[top]),ins[stc[top]]=0,top--;
	}
}
inline int nd(int x){ // x 节点是否被覆盖
	if(x>m) x-=m;
	return c[x]==0;
}
void solve(int x){
	m=g[x].size();
	for(int i=1;i<=m;i++) a[i]=g[x][m-i],c[i]=0; // 注意是 m-i，tarjan 找出来的环是反向的！！！调了好久
	for(int i=1;i<=m;i++){ // 在环上差分
		int tar=i+k-f[a[i]];
		if(tar<=m) c[i]++,c[tar+1]--;
		else c[i]++,c[1]++,c[tar-m+1]--;
	}
	for(int i=1;i<=m;i++) c[i]+=c[i-1];
	cnt=0;
	for(int i=1;i<=m;i++) if(nd(i)) b[++cnt]=i;
	cir=cnt;
	for(int i=1;i<=min(k,cnt);i++){
		int tt=0;
		for(int j=b[i];j<b[i]+m;j++)
			if(nd(j)) tt++,j+=k-1;
		cir=min(cir,tt);
	}
	ans+=cir;
}
main(){
	read(n); read(k);
	for(int i=1;i<=n;i++){
		int u,v; read(u); read(v);
		if(u==v){ to[u]=u; continue; }
		to[u]=v; deg[v]++;
	}
	for(int i=1;i<=n;i++)
		if(!dfn[i]) tarjan(i);
	for(int i=1;i<=n;i++) f[i]=k+1;
	for(int i=1;i<=n;i++)
		if(deg[i]==0 || i==1){ // 注意 i=1 的特殊处理
			if(i>1) f[i]=1,ans++;
			else f[i]=0;
			q.push(i);
		}
	while(!q.empty()){
		int u=q.front(); q.pop();
		if(f[u]>k) f[u]=1,ans++; // 距离 > k 且不在环上，给你连条边
		int v=to[u];
		if(v==1) continue;
		f[v]=min(f[v],f[u]+1);
		deg[v]--;
		if(!deg[v]) q.push(v);
	}
	for(int x=1;x<=t;x++) solve(x);
	print(ans);
}