2022 年牛客多校加赛场 B 题题解

B Bustling City

题意：给定一个 $nn$ 个点 $nn$ 条边的有向图，第 $ii$ 个点恰有一条出边指向 $a_{i}a\_i$。在每个点上恰有一个商人，一个时刻位于点 $ii$ 处的商人会走到 $a_{i}a\_i$ 号节点，问每个节点第一次有 $kk$ 个商人同时在该点的时间。$n,k\le 1\times 10^{6}n,k\; \backslash leq\; 1\backslash times\; 10^6$。

解法：将图分成若干个连通块，每个连通块由一个环和树根在环上的内向树构成。首先考虑树上的点的答案（排除树根），对于节点 $uu$，可以根据它的最大子树深度 $hh$ 得到一个长度为 $hh$ 的数组 $f_{u}f\_u$，第 $xx$ 位表示第 $xx$ 时刻它现在有多少个商人。那么这个信息是可以通过子树合并得到的：${\displaystyle f_{u,i}=\sum _{v\in {\mathrm{c}\mathrm{h}\mathrm{i}\mathrm{l}\mathrm{d}}_u}{f}_{v,i-1}}\backslash displaystyle\; f\_\{u,i\}=\backslash sum\_\{v\; \backslash in\; \{\backslash rm\; child\}\_u\}f\_\{v,i-1\}$。那么就可以进行树上启发式合并，在 $\mathcal{O}(n\log n)\backslash mathcal\; O(n\; \backslash log\; n)$ 的时间得到每个树上节点的答案。

对于环上的节点，考虑维护一个双向环形链表，初始时刻每个点均在环上。依次枚举时刻，再遍历链表，容易计算出该时刻下环上每个点的商人个数。若从某一时刻开始，环上节点 $uu$ 的子树内再也没有商人进入环中，则可将该点从链表中删除。这样看似暴力的做法复杂度其实仅为各个子树深度之和——每个环上节点只会被遍历它的子树深度层，因而可以 $\mathcal{O}(n)\backslash mathcal\; O(n)$ 的计算环上节点的答案。

因而总的复杂度为 $\mathcal{O}(n\log n+n)\backslash mathcal\; O(n\; \backslash log\; n\; +\; n)$。

#include<bits/stdc++.h>
#define IL inline
#define LL long long
#define min(a,b) (a<b?a:b)
using namespace std;
const int N=1e6+3;
struct hh{
	int pre,nxt;
}l[N];
struct kk{
	int to,nxt;
}e[N<<1];
int n,k,to[N],vis[N],bo[N],dep[N],ans[N],val[N],p,id[N];
int buk[N],siz[N],son[N],num,fir[N];
vector<int>c,d[N];
IL int in(){
  char c;int f=1;
  while((c=getchar())<'0'||c>'9')
    if(c=='-') f=-1;
  int x=c-'0';
  while((c=getchar())>='0'&&c<='9')
    x=x*10+c-'0';
  return x*f;
}
IL void add(int x,int y){e[++num]=(kk){y,fir[x]},fir[x]=num;}
void dfs(int u){
	if(vis[u]){
		int x=u;
		do{
			bo[x]=1,c.push_back(x),x=to[x];
		}while(x^u);
		return;
	}
	vis[u]=1;dfs(to[u]);
}
void dele(int x){
	l[l[x].pre].nxt=l[x].nxt,
	l[l[x].nxt].pre=l[x].pre;
}
void dfs1(int u,int f,int id){
	dep[u]=dep[f]+1,vis[u]=1;
	if(dep[u]>d[id].size()) d[id].push_back(1);
	else if(dep[u]) ++d[id][dep[u]-1];
	for(int i=fir[u],v;v=e[i].to;i=e[i].nxt)
		if(!bo[v]) dfs1(v,u,id);
}
void dfs2(int u){
	siz[u]=1;
	for(int i=fir[u],v;v=e[i].to;i=e[i].nxt)
		if(!bo[v]){
			dfs2(v),siz[u]+=siz[v];
			if(siz[son[u]]<siz[v]) son[u]=v;
		}
}
void calc(int u,int rt){
	++buk[dep[u]];
	if(buk[dep[u]]>=k+1) ans[rt]=min(ans[rt],dep[u]-dep[rt]);
	for(int i=fir[u],v;v=e[i].to;i=e[i].nxt) calc(v,rt);
}
void clear(int u){
	buk[dep[u]]=0;
	for(int i=fir[u],v;v=e[i].to;i=e[i].nxt) clear(v);
}
void dfs3(int u,int op){
	for(int i=fir[u],v;v=e[i].to;i=e[i].nxt)
		if(!bo[v]&&v^son[u]) dfs3(v,0);
	if(son[u]) dfs3(son[u],1),ans[u]=min(ans[u],ans[son[u]]+1);
	++buk[dep[u]];
	for(int i=fir[u],v;v=e[i].to;i=e[i].nxt)
		if(!bo[v]&&v^son[u]) calc(v,u);
	if(!op){
		buk[dep[u]]=0;
		for(int i=fir[u],v;v=e[i].to;i=e[i].nxt) if(!bo[v]) clear(v);
	}
}
IL int mod(int x){return x>=p?x-p:x;}
void work(int st){
	c.clear();int Max=0;
	dfs(st);dep[0]=-1;p=c.size();
	for(int i=0;i<c.size();++i) val[i]=0,dfs1(c[i],0,c[i]),dfs2(c[i]),dfs3(c[i],0);
	for(int i=0;i<c.size();++i) Max=max(Max,(int)d[c[i]].size());
	for(int i=1;i<=p;++i) l[i]=(hh){i-1,i+1};l[0].nxt=1,l[p].nxt=0,l[0].pre=p;
	Max+=c.size()+2;
	for(int i=0;i<=Max;++i){
		int now=l[0].nxt;
		while(now){
			int u=c[now-1];
			if(d[u].size()>i){
				int pre=mod((now-i-1)%p+p);
				val[pre]+=d[u][i];
				if(val[pre]>=k) ans[u]=min(ans[u],i+1);
				now=l[now].nxt;
			}
			else dele(now),now=l[now].nxt;
		}
	}
	int Min=1e9,pos=0;
	for(int i=0;i<c.size();++i)
	  if(Min>ans[c[i]]) Min=ans[c[i]],pos=i;
	for(int i=mod(pos+1);i!=pos;i=mod(i+1)){
		++Min,Min=ans[c[i]]=min(ans[c[i]],Min);
	}
}
void solve(){
	n=in(),k=in();c.clear();
	for(int i=1;i<=n;++i) ans[i]=1e9,to[i]=in(),add(to[i],i);
	--k;
	for(int i=1;i<=n;++i) if(!vis[i]) work(i);
	for(int i=1;i<=n;++i)
	  if(ans[i]==1e9) printf("-1 ");
	  else printf("%d ",ans[i]);
}
int main()
{
	int T=1;
	while(T--) solve();
  return 0;
}