P6753 [BalticOI 2013 Day1] Ball Machine 题解

lyhqwq · 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;
}