题意

$~~~~$ 给出内向基环树森林，求最少加多少条边使得 $1$ 到每个点的最短路均不超过 $k$

题解

$~~~~$ 吐槽翻译题目的人，内向基环树都没翻出来。

$~~~~$ 显然 $1$ 连其他点是最优的，原因不必过多赘述。

$~~~~$ 一次我们考虑一棵基环树，其他的树同理。我们先把环丢掉，叶子节点肯定是要连边的（没有给它连边的点，即本身不可达），顺次向上，我们就可以找到每次要连边的点。

$~~~~$ 然后，对于环上所有不满足条件的点，我们单独提出来，枚举以哪个为起点，每次连向它（这里是假连，实际是跳过它后面的 $k-1$ 个点）后跳 $k$ 步，在跳 $k$ 步后的节点找到下一个不满足条件的点（可能是自己）。

$~~~~$ 发现这样的话枚举 $k$ 个点以上时就会造成重复（只是把某次情况起点改为后移 $k$ 步后的第一个点），因此枚举 $k$ 个点即可。

时间复杂度：$\mathcal{O(\dfrac{n}{k})\times k}=\mathcal{O(n)}$

代码

#include<bits/stdc++.h>
using namespace std;

vector <int> G[1000005];//存反图，算距离
int n,k,To[1000005]/*每个点的出边连向的点*/,In[1000005]/*入度*/,dis[1000005],ans,cov[1000005],nxt[1000005]/*跳k步后的点*/;
bool On[1000005]/*是否在环上*/,vis[1000005]/*是否遍历过*/,isCov[1000005]/*是否已经覆盖该环上的点*/;
vector <int> cyc;//存每次的环

void dfs(int u)//倒着来求距离及给树上不满足的点加边
{
	vis[u]=true;
//	if(!In[u]){dis[u]=u!=1;ans+=u!=1;return;}
	dis[u]=1e9;
	for(int i=0;i<(int)G[u].size();i++)
	{
		int v=G[u][i];
		if(On[v]) continue;
		dfs(v);dis[u]=min(dis[u],dis[v]+1);
	}
	if(u==1) dis[u]=0;
	if(!On[u]&&dis[u]>k) dis[u]=1,ans++;
}

int main() {
//	freopen("1.in","r",stdin);
	scanf("%d %d",&n,&k);
	for(int i=1;i<=n;i++) {
		G[i].clear();
		vis[i] = false;
		On[i] = false;
	}
	for(int i=1,x,y;i<=n;i++)
	{
		scanf("%d %d",&x,&y);To[x]=y;
		In[y]++;G[y].push_back(x);
	}
	for(int i=1;i<=n;i++)
	{
		if(!vis[i])
		{
			cyc.clear();int x=i;cyc.push_back(233);
			while(!vis[x]) vis[x]=true,x=To[x];//找环
			cyc.push_back(x);On[x]=true;
			int y=To[x];
			while(y!=x) cyc.push_back(y),On[y]=true,y=To[y];
			int cnt=cyc.size()-1;
			for(int j=1;j<=cnt;j++) dfs(cyc[j]),cov[j]=cov[j+cnt]=0;
			for(int j=1;j<=cnt;j++)//差分找每个点是否覆盖
			{
				if(dis[cyc[j]]<=k)
				{
					cov[j]++;
					if(j+k-dis[cyc[j]]<cnt<<1) cov[j+k-dis[cyc[j]]+1]--;
				}
			}
			for(int j=1;j<=cnt<<1;j++) cov[j]+=cov[j-1];
			for(int j=1;j<=cnt;j++)
			{
				if(cov[j]||cov[j+cnt]) isCov[j]=isCov[j+cnt]=1;
				else isCov[j]=isCov[j+cnt]=0;	
			}
			nxt[(cnt<<1)+1]=(cnt<<1)+1;
			for(int j=cnt<<1;j;j--)
			{
				if(isCov[j]) nxt[j]=nxt[j+1];
				else nxt[j]=j;	
			}
			int Searched=0,Minn=1e9;
			for(int j=1;j<=cnt;j++)//枚举换上的点
			{
				if(isCov[j]) continue;
				int Tmp=0;
				for(x=j;x<j+cnt;)
				{
					Tmp++,x+=k;
					if(x<cnt+j) x=nxt[x];
				}
				Minn=min(Minn,Tmp);
				if(++Searched==k) break;//枚举到k个直接停止
			}
			if(Minn<1e9) ans+=Minn;
		}
	}
	printf("%d",ans);
	return 0;
}