[BZOJ3133] [Baltic2013]ballmachine(树上倍增+堆)

题面

有一个装球机器，构造可以看作是一棵树。有下面两种操作：

从根放入一个球，只要下方有空位，球会沿着树滚下。如果同时有多个点可以走，那么会选择编号最小的节点所在路径的方向。比如依次在树根4放2个球，第一个球会落到1，第二个会落到3：

从某个位置拿走一个球，那么它上方的球会落下来。比如依次拿走5, 7, 8三个球：

分析

我们可以预处理出从根节点放第i个球时,球到达的位置x.因此，对于每个节点x，我们记录放第几个球的时候才能落到x,记为seq[x]。

预处理的时候先dfs一遍，求出每个节点子树中的最小节点编号。然后再dfs一遍，按照子树中的最小节点编号从小到大遍历。实现上直接sort一遍邻接表即可。容易发现，seq[x]就是x在树的后序遍历序列中处在第几个(因为球会尽量往最下方走)

void dfs2(int x,int fa){
	for(int i=0;i<(int)E[x].size();i++){//E[x]已经排过序
		int y=E[x][i];
		if(y!=fa){
			dfs2(y,x);
		}
	} 
	seq[x]=++tim;
	hash_seq[seq[x]]=x;
}

然后考虑动态插入和删除。

维护一个最小堆，满足堆顶元素seq最小。插入的时候弹出堆顶，把堆顶对应的节点的状态标记为有球。

删除节点x的时候,x到根节点链上的节点会往下落一层。因此只需要用树上倍增找到x祖先里深度最浅的有球节点，将它的状态标记为无球，然后插入最小堆.

代码

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<cmath>
#include<vector>
#include<algorithm>
#define maxn 100000
#define maxlogn 21 
using namespace std;
int n,m;
int root;
vector<int>E[maxn+5];

int log2n;
int min_id[maxn+5];//子树中节点的最小编号 
int anc[maxn+5][maxlogn+5];
int deep[maxn+5];
bool cmp(int x,int y){
	return min_id[x]<min_id[y];
}
void dfs1(int x,int fa){
	min_id[x]=x;
	deep[x]=deep[fa]+1;
	anc[x][0]=fa;
	for(int i=1;i<=log2n;i++) anc[x][i]=anc[anc[x][i-1]][i-1];
	for(int i=0;i<(int)E[x].size();i++){
		int y=E[x][i];
		if(y!=fa){
			dfs1(y,x);
			min_id[x]=min(min_id[x],min_id[y]);
		}
	} 
}

int tim;
int seq[maxn+5]; //掉球顺序 
int hash_seq[maxn+5];//seq=i的节点编号 
int is_ball[maxn+5];//是否有球 
priority_queue<int,vector<int>,greater<int> >q;//按落球顺序从小到大，存储没有球的节点 
void dfs2(int x,int fa){
	for(int i=0;i<(int)E[x].size();i++){
		int y=E[x][i];
		if(y!=fa){
			dfs2(y,x);
		}
	} 
	seq[x]=++tim;
	hash_seq[seq[x]]=x;
}

int insert(int num){
	int ans;
	for(int i=1;i<=num;i++){
		int x=hash_seq[q.top()];
		q.pop();
		is_ball[x]=1;
		if(i==num){
			ans=x;
			break;
		} 
	}
	return ans;
}
int del(int x){
	int orig_x=x;
	for(int i=log2n;i>=0;i--){
		if(is_ball[anc[x][i]]) x=anc[x][i];
	}
	is_ball[x]=0;
	q.push(seq[x]);
	return deep[orig_x]-deep[x];
}

int main(){
	int f;
	int op,num;
	scanf("%d %d",&n,&m);
	log2n=log2(n)+1;
	for(int i=1;i<=n;i++){
		scanf("%d",&f);
		if(f==0) root=i;
		else E[f].push_back(i);
	} 
	dfs1(root,0);
	for(int i=1;i<=n;i++) sort(E[i].begin(),E[i].end(),cmp);
	dfs2(root,0);
	for(int i=1;i<=n;i++) q.push(seq[i]);
	for(int i=1;i<=m;i++){
		scanf("%d %d",&op,&num);
		if(op==1) printf("%d
",insert(num));
		else printf("%d
",del(num));
	}
}