自动搬运

查看原文

来自洛谷，原作者为

	lyhqwq D

搬运于2025-08-24 22:23:38，当前版本为作者最后更新于2023-10-04 22:07:59，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

Solution

一道水紫

首先考虑放球操作

观察到小球每次下落必然选择子树内编号最小的点所在的子树下落，所以我们可以先预处理出 $Min_u$ 表示以 $u$ 为根的子树内编号最小的节点。

之后将每个结点的出边按照 $Min$ 从小到大排序，预处理出 dfs 序，那么小球每次下落选择的一定是当前没有小球且 dfs 序最小的节点，可以用一个优先队列来维护。

接着考虑撤球操作，如果一个球被撤掉了，那么从这个节点到根的这条链上所有的球都会向下一个，所以可以倍增找到这条链上第一个没有球的结点，深度之差即为答案。

对于放球操作，每放一个球时间复杂度为 $O(\log n)$，因为总共最多放 $n+\dfrac{Q}{2}$ 个球，所以总的时间复杂度为 $O((n+Q)\log n)$，可以通过本题。

Code

#include<bits/stdc++.h>
using namespace std;
const int N=100005;
int n,Q,rt;
int vis[N];
int dfn[N],rnk[N],cnt;
int dep[N],f[N][18];
int Min[N];
vector<int> vec[N];
priority_queue<int,vector<int>,greater<int> > q;
bool cmp(int x,int y){
	return Min[x]<Min[y];
}
void dfs1(int u){
	Min[u]=u,dep[u]=dep[f[u][0]]+1;
	for(int i=1;i<=17;i++) f[u][i]=f[f[u][i-1]][i-1];
	for(int i=0;i<vec[u].size();i++){
		int v=vec[u][i];
		dfs1(v);
		Min[u]=min(Min[u],Min[v]);
	}
}
void dfs2(int u){
	for(int i=0;i<vec[u].size();i++){
		int v=vec[u][i];
		dfs2(v);
	}
	dfn[u]=++cnt,rnk[cnt]=u;
}
int main(){
	//freopen(".in","r",stdin);
	//freopen(".out","w",stdout);
	scanf("%d%d",&n,&Q);
	for(int i=1;i<=n;i++){
		scanf("%d",&f[i][0]);
		if(!f[i][0]) rt=i;
		else vec[f[i][0]].push_back(i);
	}
	dfs1(rt);
	for(int i=1;i<=n;i++) sort(vec[i].begin(),vec[i].end(),cmp);
	dfs2(rt);
	for(int i=1;i<=n;i++) q.push(i);
	while(Q--){
		int op,x;
		scanf("%d%d",&op,&x);
		if(op==1){
			int ans=0; 
			for(int i=1;i<=x;i++){
				ans=q.top();
				q.pop();
				vis[rnk[ans]]=1;
			}
			printf("%d\n",rnk[ans]);
		}
		else{
			int ans=0,y=x;
			for(int i=17;~i;i--) if(vis[f[y][i]]) y=f[y][i];
			vis[y]=0;
			q.push(dfn[y]);
			printf("%d\n",dep[x]-dep[y]);
		}
	}
	return 0;
}