CF1137F 题解

lmh_qwq · 2025-11-18 15:28:20 · 题解

先把无根树转化为有根树，可以令编号最大的点为根——它必定最后被删除。

之后考虑一次查询过程，查询 x 时找出子树内 p 最大的节点 y，显然是 y 把它卡住了删不掉。之后标记所有 p_i\ge p_y 的节点和其祖先，必定是把树删到只剩下这些节点，然后从 y 一路删到 x。

这已经可以处理比较操作了，但为了解决查询操作需要找出所有 p_i\ge p_y 的节点，求包含它们的最小连通块（注意到根节点的 p 一定 \ge p_y）的节点数量。

令 1 为根，把所有特殊节点按照 dfs 序排序。之后求出它们的深度之和减去相邻两个位置的 LCA 深度之和，得到的就是包含这些节点和 1 的最小连通块大小；为了去掉根节点的影响，求出所有节点的 LCA（也就是 dfs 序最小和最大的节点的 LCA）即可。

但是我们还需要快速找出这些节点。注意到全程一个 p 至多出现一次，可以令 a_i 代表唯一一个存在任意时刻满足 p_x=i 的 x。

之后找出 p_i\ge p_y 的节点就相当于取出 a 上面 [p_y, p_r] 这一段（r 为当前 p 最大的节点）。

现在尝试用莫队维护一个特殊点组成的集合，需要在维护的集合中插入或者删除一个点。求 LCA 可以做到单次 O(1)，但是在集合中插入删除点需要找到它两侧的第一个点，这需要 O(\log n) 的复杂度，无法接受。

利用这个题的技巧，使用只删除的回滚莫队，这样维护一个按照 dfs 序排好序的双向链表，就能直接查询前驱后继。

综上，假设 n,q 同阶，总复杂度 O(n\sqrt n)，需要注意算法常数。

#include<bits/stdc++.h>
using namespace std;
#define ll int
#define lson (u<<1)
#define rson (u<<1|1)
const ll N=200007,B=700;
int n,m,k,nQ,w[N],a[N<<1];
int p[N],dep[N],id[N],tI[N],tO[N],timer,c[N];
int type[N],ans[N],iB[N<<1];
int pre[N],nxt[N],cnt[N],L,R,now;
vector<int> to[N];
char op[10];
struct query{
    int u,l,r,id;
}qry[N<<1];
bool up(int u,int v){
    return tI[u]<=tI[v]&&tO[v]<=tO[u];
}
namespace SGT{
    int pos[N<<2];
    int cmp(int x,int y){return w[x]>w[y]?x:y;}
    void build(int u,int l,int r){
        if (l==r){
            pos[u]=id[l];
            return;
        }
        int mid=l+r>>1;
        build(lson,l,mid);
        build(rson,mid+1,r);
        pos[u]=cmp(pos[lson],pos[rson]);
    }
    void modify(int u,int l,int r,int x){
        if (l==r){
            return;
        }
        int mid=l+r>>1;
        if (x<=mid){
            modify(lson,l,mid,x);
        }
        else{
            modify(rson,mid+1,r,x);
        }
        pos[u]=cmp(pos[lson],pos[rson]);
    }
    int query(int u,int l,int r,int L,int R){
        if (L<=l&&r<=R){
            return pos[u];
        }
        int mid=l+r>>1;
        if (R<=mid){
            return query(lson,l,mid,L,R);
        }
        if (L>mid){
            return query(rson,mid+1,r,L,R);
        }
        return cmp(query(lson,l,mid,L,R),query(rson,mid+1,r,L,R));
    }
}
namespace ST{
    int mn[20][N],st[20][N];
    int cmp(int x,int y){
        return dep[x]<dep[y]?x:y;
    }
    void build(){
        for (int i=1;i<=n;++i){
            mn[0][i]=id[i];
            st[0][i]=dep[id[i]];
        }
        for (int p=1;p<20;++p){
            for (int i=1;i<=n-(1<<p)+1;++i){
                mn[p][i]=cmp(mn[p-1][i],mn[p-1][i+(1<<p-1)]);
                st[p][i]=min(st[p-1][i],st[p-1][i+(1<<p-1)]);
            }
        }
    }
    int query(int l,int r){
        int k=__lg(r-l+1);
        return cmp(mn[k][l],mn[k][r-(1<<k)+1]);
    }
    int query_dep(int l,int r){
        int k=__lg(r-l+1);
        return min(st[k][l],st[k][r-(1<<k)+1]);
    }
}
int LCA(int u,int v){
    if (u==v){
        return u;
    }
    if (tI[u]>tI[v]){
        return p[ST::query(tI[v]+1,tI[u])];
    }
    return p[ST::query(tI[u]+1,tI[v])];
}
int get_max_value(int root,int u){
    if (up(u,root)){
        u=ST::query(tI[u]+1,tI[root]);
        if (tO[u]==n){
            return SGT::query(1,1,n,1,tI[u]-1);
        }
        return SGT::cmp(SGT::query(1,1,n,1,tI[u]-1),SGT::query(1,1,n,tO[u]+1,n));
    }
    return SGT::query(1,1,n,tI[u],tO[u]);
}
int dis(int u,int v){
    return dep[u]+dep[v]-2*dep[LCA(u,v)];
}
void dfs(int u,int fa){
    p[u]=fa;dep[u]=dep[fa]+1;tI[u]=++timer;id[timer]=u;
    for (auto v:to[u]){
        if (v==fa){
            continue;
        }
        dfs(v,u);
    }
    tO[u]=timer;
}
namespace SGT2{
    ll val[N<<3];
    void build(int u,int l,int r){
        if (l==r){
            val[u]=dep[LCA(a[l-1],a[l])]-1;
            return;
        }
        int mid=l+r>>1;
        build(lson,l,mid);build(rson,mid+1,r);
        val[u]=min(val[lson],val[rson]);
    }
    int query(int u,int l,int r,int L,int R){
        if (L<=l&&r<=R){
            return val[u];
        }
        int mid=l+r>>1;
        if (R<=mid){
            return query(lson,l,mid,L,R);
        }
        if (L>mid){
            return query(rson,mid+1,r,L,R);
        }
        return min(query(lson,l,mid,L,R),query(rson,mid+1,r,L,R));
    }
}
int main(){
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    cin>>n>>m;
    k=n;
    for (int u,v,i=1;i<n;++i){
        cin>>u>>v;
        to[u].emplace_back(v);to[v].emplace_back(u);
    }
    dfs(1,0);
    ST::build();
    for (int i=1;i<=n;++i){
        w[i]=a[i]=i;c[i]=1;
    }
    SGT::build(1,1,n);
    auto add_query=[&](int u,int id){
        if (u==a[k]){
            ans[id]=n;
            return;
        }
        int v=get_max_value(a[k],u);
        qry[++nQ]=(query){u,w[v],k,id};
        ans[id]=n+dis(u,v)+1;
    };
    for (int u,v,i=1;i<=m;++i){
        cin>>op;
        type[i]=op[0];
        if (op[0]=='u'){
            cin>>u;
            a[++k]=u;++c[u];
            w[u]=k;
            SGT::modify(1,1,n,tI[u]);
        }
        else if (op[0]=='w'){
            cin>>u;
            add_query(u,i);
        }
        else{
            cin>>u>>v;
            if (u==a[k]||v==a[k]){
                ans[i]=u^v^a[k];
            }
            else{
                int U=get_max_value(a[k],u),V=get_max_value(a[k],v);
                if (U!=V){
                    ans[i]=(w[U]<w[V]?u:v);
                }
                else{
                    ans[i]=(dis(u,U)<dis(v,V)?u:v);
                }
            }
        }
    }
    for (int l=1,r,o=0;l<=k;l=r+1){
        r=min(k,l+B-1);
        ++o;
        for (int i=l;i<=r;++i){
            iB[i]=o;
        }
    }
    sort(qry+1,qry+1+nQ,[&](const query& a,const query& b){
        return iB[a.l]==iB[b.l]?a.r>b.r:a.l<b.l;
    });
    auto del=[&](const int& x){
        if (--cnt[x]){
            return;
        }
        int l=pre[x],r=nxt[x];
        nxt[l]=r;pre[r]=l;
        now-=dep[id[x]]+ST::query_dep(l+1,r)-ST::query_dep(l+1,x)-ST::query_dep(x+1,r)+1;
    };
    auto add=[&](const int& x){
        if ((++cnt[x])==1){
            nxt[pre[x]]=pre[nxt[x]]=x;
        }
    };
    now=n;L=1;R=k;
    int A=n;
    for (int i=1;i<=n;++i){
        cnt[i]=c[id[i]];
        pre[i]=i-1;nxt[i]=i+1;
    }
    SGT2::build(1,2,k);
    for (int t=1;t<=nQ;++t){
        if (iB[qry[t].l]!=iB[qry[t-1].l]){
//          cerr<<iB[qry[t].l]<<' '<<t<<endl;
            now=A;
            while(R<k){
                add(tI[a[++R]]);
            }
            while(iB[L]!=iB[qry[t].l]){
                del(tI[a[L++]]);
            }
            A=now;
        }
        while(R>qry[t].r){
            del(tI[a[R--]]);
        }
        int tnow=now,tl=L;
        while(L<qry[t].l){
            del(tI[a[L++]]);
        }
        ans[qry[t].id]-=now-SGT2::query(1,2,k,qry[t].l+1,qry[t].r);
        while(L>tl){
            add(tI[a[--L]]);
        }
        now=tnow;
    }
    for (int i=1;i<=m;++i){
        if (type[i]=='w'||type[i]=='c'){
            cout<<ans[i]<<'\n';
        }
    }
    return 0;
}