题解：P4116 Qtree3

· · 题解

提供一种和目前其他题解不同的做法。

这题树剖完之后其实就是要维护一种数据结构支持：（初始所有序列上所有数为 0）每次将一个序列上的一个数由 0 变为 1 或由 1 变为 0，或者查询一个序列中编号最小的数 1。

对于查询操作，我们可以想到用倍增的方式去处理：从大到小枚举 i，如果当前位置向后 2^i 位都没有 1，那么就更新当前位置到 2^i 之后。

由于询问的特殊性，当前位置一定是从 0 开始的。然后我们惊奇地发现，这种查询方式是可以用树状数组维护的！“当前位置向后 2^i 位”刚好就是某个 j-\mathrm{lowbit}(j) 到 j，因此可以用树状数组 O(1) 得到。这其实很好理解，因为树状数组查询的时候就是用的上面的倍增的方式，只不过是反过来的。

然后就是代码了，虽然没有 set 好写，但个人认为比线段树好写。

#include<bits/stdc++.h>
using namespace std;
#define N 100010
int n,q;
int f[N],siz[N],sw[N];
vector<int>t[N];
void dfs1(int fa,int u){
    siz[u]=1;sw[u]=0;f[u]=fa;
    for(int i=0;i<t[u].size();i++){
        if(t[u][i]==fa)continue;
        dfs1(u,t[u][i]);
        siz[u]+=siz[t[u][i]];
        if(siz[t[u][i]]>siz[sw[u]])sw[u]=t[u][i];
    }
}
int cnt,dfn[N],fdfn[N],top[N],sizt[N];
//这里记录sizt数组为一条重链的最浅点所在重链的长度 
void dfs2(int u){
    if(u==1)top[u]=u,sizt[u]=1;
    dfn[u]=++cnt;fdfn[cnt]=u;
    if(sw[u]){
        top[sw[u]]=top[u];
        sizt[top[u]]++;
        dfs2(sw[u]);
    }
    for(int i=0;i<t[u].size();i++){
        if(t[u][i]==f[u]||t[u][i]==sw[u])continue;
        top[t[u][i]]=t[u][i],sizt[t[u][i]]=1;
        dfs2(t[u][i]);
    }
}
int ta[N],a[N],log_2[N];
//ta是树状数组，这里就直接维护区间和了 
void init(){
    for(int i=2;i<=n;i++)log_2[i]=log_2[i>>1]+1;
}
void add(int u,int k){
    int x=dfn[u]-dfn[top[u]]+1;
    for(int i=x;i<=sizt[top[u]];i+=i&(-i))
        ta[i+dfn[top[u]]-1]+=k;
        //树状数组的修改，注意一下下标就行了 
}
int query(int u){
    int p=-1;
    while(u){
        int x=0;
        for(int j=log_2[sizt[top[u]]];j>=0;j--)
            if(x+(1<<j)<=sizt[top[u]])
                if(ta[x+(1<<j)+dfn[top[u]]-1]==0)
                    x+=(1<<j);
                //如果区间和为0说明区间里没有1 
        x++;
        if(x<=dfn[u]-dfn[top[u]]+1)
            p=fdfn[dfn[top[u]]+x-1];
            //如果第一个1深度小于等于u，就记录 
        u=f[top[u]];
    }
    return p;
}
signed main(){
    ios::sync_with_stdio(0);cin.tie(0);
    cin>>n>>q;
    init();
    for(int i=1,u,v;i<n;i++)
        cin>>u>>v,t[u].push_back(v),t[v].push_back(u);
    dfs1(0,1);
    dfs2(1);
    while(q--){
        int op,x;
        cin>>op>>x;
        if(op)cout<<query(x)<<'\n';
        else{
            if(a[x])add(x,-1),a[x]=0;
            else add(x,1),a[x]=1;
        }
    }
    return 0;
}