“蔚来杯“2022牛客暑期多校训练营（加赛） B题: Bustling City

B题: Bustling City

原题链接:https://ac.nowcoder.com/acm/contest/38727/B

题目大意

有 $n(1\le n\le 10^6)$ 个城市，第 $i$ 个城市有一个商人，和一条城市 $i$ 通往城市 $a_i$ 的双向道路。

每年年初，城市 $i$ 的所有商人会前往城市 $a_i$ 。

求每个城市最早在哪一年有至少 $k$ 个商人。

题解

显然，输入为一张内向基环森林。
考虑将每棵基环树分为树和环两部分进行求解。
树上部分可以通过维护每个点的若干级儿子来求解，这个信息是可以从儿子传递到父亲的，通过长链剖分，每次将其他儿子的信息暴力转移到长链上对应深度的点可以做到 $O(\sum len)=O(n)$ 的复杂度。
对于环上部分，考虑其子树上的点何时会转移到它，可以根据子树中的点到根的距离等价映射到环上的一个前置点。
参考下图:

图中黑色为原本的边，绿框内部分为环，我们将环外的子树内的点，根据相对距离标记到环上的对应的点。
显然，子树内深度相同的点的标记位置是相同的，因此我们可以利用前面长链剖分中已经统计的每个深度对应的节点数。
当环上某个点的一个前置点的人数能够达到 $k$ 个时，我们对其计算所需步数。
然后枚举环上每一个点，考虑从其他已经计算过的点走到他还需要几步，选取最小值，这个可以用一个 $multiset$ 维护。
总复杂度 $O(nlogn)$ ，可以通过。

注意点

1. 处理子树问题时可以反向建边( $a_i\to i$ )，将基环内向树转化为外向树。
2. 因为是森林，记得多次初始化清空。

参考代码

#include
using namespace std;

template<class T>inline void read(T&x){
	char c,last=' ';
	while(!isdigit(c=getchar()))last=c;
	x=c^48;
	while(isdigit(c=getchar()))x=(x<<3)+(x<<1)+(c^48);
	if(last=='-')x=-x;
}

const int MAXN=1e6+5,INF=0x3f3f3f3f;
int n,k;
int a[MAXN];
int vis[MAXN];//是否访问过
int dep[MAXN];//深度
int max_dep[MAXN];//子树内最大深度(求长儿子)
int _son[MAXN];//长儿子
int cnt[MAXN];//维护长链上等深度的节点个数
int dp[MAXN];//当前点往下最小有k个同层节点的深度
int num[MAXN];//环上某个前置点的等价点个数
int when[MAXN];//预计算的个数
int ans[MAXN];//答案
vector<int>loop;//环上的点
vector<int>e[MAXN];//边(反向)
vector<int>chain[MAXN];//环上每个点的子树内的长链信息

struct node{
	int p,length;//p表示子树的根是环上第p个点,length表示长链的长度
}infor[MAXN];

bool cmp(const node&a,const node&b){
	return a.length<b.length;
}

int find_loop(int x){//寻找环
	if(vis[x])return x;//找到了一个已访问过的点(即找到了环)
	vis[x]=1;
	loop.push_back(x);
	return find_loop(a[x]);
}

void _dfs(int x,int depth){//预搜索,求长儿子
	max_dep[x]=dep[x]=depth;
	for(int i=0,son;i<(int)e[x].size();++i){
		son=e[x][i];
		if(vis[son])continue;
		_dfs(son,depth+1);
		if(max_dep[son]>max_dep[_son[x]])_son[x]=son;//有更长的链,更新长儿子
		max_dep[x]=max(max_dep[x],max_dep[son]+1);//更新最大深度
	}
}

void dfs(int x){
	cnt[x]=1;
	vis[x]=1;
	if(_son[x]){//先搜长链
		dfs(_son[x]);
		dp[x]=min(dp[x],dp[_son[x]]);
	}
	for(int i=0;i<(int)e[x].size();++i){
		int son=e[x][i];
		if(vis[son])continue;
		dfs(son);
		dp[x]=min(dp[x],dp[son]);
		int main=_son[x];//长链上的对应点
		while(son){
			cnt[main]+=cnt[son];//将信息转移到长链上
			if(cnt[main]>=k)dp[x]=min(dp[x],dep[main]);//更新一下达到k人所需的最小深度
			son=_son[son],main=_son[main];
		}
	}
	if(dp[x]<INF)ans[x]=dp[x]-dep[x];//可以达到k人,计算答案
}

void solve(int I){
	vector<int>().swap(loop);
	int head=find_loop(I);
	vector<int>pool;
	for(int i=0;i<(int)loop.size();++i){
		if(loop[i]!=head)vis[loop[i]]=0;//除去搜索时那些不属于环上的点
		else{
			for(int j=i;j<(int)loop.size();++j){
				pool.push_back(loop[j]);
			}
			break;
		}
	}
	loop=pool;
	int m=(int)loop.size();
	for(int i=0;i<m;++i){
		_dfs(loop[i],0),dfs(loop[i]);
		int x=loop[i];
		vector<int>().swap(chain[i]);
		while(x){
			chain[i].push_back(cnt[x]);//保存长链的信息
			x=_son[x];
		}
		infor[i].p=i,infor[i].length=(int)chain[i].size();
	}
	sort(infor,infor+m,cmp);//按照链长排序
	int l=0;
	for(int i=0;i<m;++i)num[i]=0,when[i]=INF;
	for(int i=0;i<infor[m-1].length;++i){//从小到大枚举子树内点到环上的距离
		while(infor[l].length<i+1)++l;//除去那些最大深度不到i的子树
		for(int j=l;j<m;++j){
			int p=((infor[j].p-i)%m+m)%m;//前置点
			num[p]+=chain[infor[j].p][i];
			if(num[p]>=k){//可达k人
				when[infor[j].p]=min(when[infor[j].p],i);//从前置点到此处需k步
			}
		}
	}
	multiset<int>st;
	for(int i=0;i<m;++i)if(when[i]<INF)st.insert(when[i]+m-i);//这些点转移的方向是S->m->1->T(绕一圈)
	for(int i=0;i<m;++i){
		if(when[i]<INF){//对于<=i的点,转移方向是S->T(不需要绕圈)
			st.erase(st.find(when[i]+m-i));
			st.insert(when[i]-i);
		}
		if(!st.empty())ans[loop[i]]=(*st.begin())+i;
	}
}

int main()
{
	read(n),read(k);
	for(int i=1;i<=n;++i){
		read(a[i]);
		e[a[i]].push_back(i);
		ans[i]=-1;
		dp[i]=INF;
	}
	for(int i=1;i<=n;++i)if(!vis[i])solve(i);
	for(int i=1;i<=n;++i)cout<<ans[i]<<" \n"[i==n];
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137