题解：P4116 Qtree3

· · 题解

观测到题解区没有树上带修莫队做法，我来写一篇。

本题有两种操作，要求维护单点翻转和路径深度最小的黑点（以点 1 为根）。对于点 x 的翻转，直接 a_x\leftarrow a_x\oplus 1，区间查询可以对于深度值域分块，维护距离根（点 1）最近，也就是深度最小的黑点。

时间复杂度 O(n^\frac{5}{3})，在 n=10^5 的情况下约为 2\times10^8，可过。

本题不卡常，放心做。

:::info[如果你不知道树上莫队] 对树进行 dfs，每个点 x 进入和离开时向序列加入 x，把树压成括号序列，定义数组 f_x 为 x 进入的位置，g_x 为 x 离开的位置。

下面考虑一条路径 (u,v) 如何映射在序列上（以下令 f_u\le f_v）。

因为无用节点出现 0 或 2 次，维护 vis_x 代表 x 节点出现次数的奇偶性，遇到新数时 vis_x 为 1 则删除，为 0 则加入。

其实跑得还不算很慢，最慢点两百毫秒。

:::success[code]

#include<bits/stdc++.h>
#define int unsigned int
#define endl '\n'
#define pb push_back
using namespace std;
const int N=2e6+5;
const int B2=450;
int n,m,B,a[N],b[N],idx,cnt[N],id[N],f[N],g[N],fa[N],dfn[N],top[N],siz[N],dep[N],son[N],cntq,cntu,last[N],cur,ans[N],vb[N];
bool vis[N];
int cntdep[N],vb2[N],depn[N];
struct qry{
    int l,r,t,x,typ,lca;
}q[N];
struct upd{
    int x;
}up[N];
bool cmp(qry a,qry b){
    if(a.l/B!=b.l/B) return a.l<b.l;
    else if(a.r/B!=b.r/B){
        if(a.l/B&1) return a.r<b.r;
        else return a.r>b.r;
    }
    else{
        if(a.r/B&1) return a.t<b.t;
        else return a.t>b.t;
    }
}
vector<int> G[N];
void dfs1(int x,int ft){
    id[f[x]=++idx]=x;
    dep[x]=dep[ft]+1;
    siz[x]=1;
    fa[x]=ft;
    for(auto i:G[x]){
        if(i==ft) continue;
        dfs1(i,x);
        siz[x]+=siz[i];
        if(siz[i]>siz[son[x]]) son[x]=i;
    }
    id[g[x]=++idx]=x;
}
void dfs2(int x,int tp){
    top[x]=tp;
    if(son[x]) dfs2(son[x],tp);
    for(auto i:G[x]) if(i!=fa[x]&&i!=son[x]) dfs2(i,i);
}
int lca(int x,int y){
    while(top[x]!=top[y]){
        if(dep[top[x]]<dep[top[y]]) swap(x,y);
        x=fa[top[x]];
    }
    if(dep[x]>dep[y]) swap(x,y);
    return x;
}
inline void insert(int x){
    int d=dep[x];
    if(cntdep[d]==0) vb2[d/B2]++;
    cntdep[d]++;
    depn[d]=x;
}
inline void erase(int x){
    int d=dep[x];
    cntdep[d]--;
    if(cntdep[d]==0) vb2[d/B2]--;
}
inline int query(){
    for(int b=0;b<=n/B2+1;b++){
        if(vb2[b]){
            int R=min(n,(b+1)*B2-1);
            for(int d=b*B2;d<=R;d++){
                if(cntdep[d]) return depn[d];
            }
        }
    }
    return -1;
}
inline void add(int x){
    if(vis[x]){
        if(a[x]) erase(x);
        vis[x]=0;
    }else{
        if(a[x]) insert(x);
        vis[x]=1;
    }
}
inline void update(int x){
    if(vis[x]){
        if(a[x]) erase(x);
        a[x]=a[x]^1;
        if(a[x]) insert(x);
    }else a[x]=a[x]^1;
}
char ibuf[1<<20],*p1=ibuf,*p2=ibuf;
#define gc() (p1==p2&&(p2=(p1=ibuf)+fread(ibuf,1,1<<20,stdin),p1==p2)?EOF:*p1++)
inline int read(){
    int x=0,f=1;char c=gc();
    while(c<'0'||c>'9'){ if(c=='-') f=-1; c=gc(); }
    while(c>='0'&&c<='9') x=(x<<3)+(x<<1)+(c^48), c=gc();
    return x*f;
}
char obuf[1<<20],*pp=obuf;
inline void push(char c){
    if(pp-obuf==(1<<20))fwrite(obuf,1,1<<20,stdout),pp=obuf;
    *pp++=c;
}
inline void write(signed x){
    if(x<0){ push('-'); x=-x; }
    static signed st[12]; signed top=0;
    if(!x) push('0');
    while(x) st[++top]=x%10, x/=10;
    while(top) push(st[top--]^48);
    push('\n');
}
inline void readstr(char *s){
    char c=gc();
    while(c<=' ') c=gc();
    while(c>' ') *s++=c, c=gc();
    *s=0;
}
signed main(){
    n=read();
    m=read();
    for(int i=1,u,v;i<n;i++){
        u=read();
        v=read();
        G[u].pb(v);
        G[v].pb(u); 
    }
    dfs1(1,0);
    dfs2(1,1);
    for(int i=1,v,op;i<=m;i++){
        op=read();
        v=read();
        if(op==1){
            int L=lca(1,v);
            q[++cntq]={L==1?f[1]:g[1],f[v],cntu,cntq,1,L};
        }
        else{
            up[++cntu]={v};
        }
    }
    B=pow(2*n,2.0/3)*pow(cntu,1.0/3)/pow(cntq,1.0/3);
    sort(q+1,q+cntq+1,cmp);
    int r=0,t=0;
    for(int i=1;i<=cntq;i++){
        while(r<q[i].r) add(id[++r]);
        while(r>q[i].r) add(id[r--]);
        while(t<q[i].t) t++,update(up[t].x);
        while(t>q[i].t) update(up[t].x),t--;
        add(1);
        ans[q[i].x]=query();
        add(1);
    }
    for(int i=1;i<=cntq;i++) write((signed)ans[i]);
    fwrite(obuf,1,pp-obuf,stdout);
    return 0;
}

:::