题解：P14889 Key Point

· · 题解

不需要哈希的做法。

这是一棵没有环的树，从某个起点出发一直在树上走，最终一定停在某个没有出边的节点。如果 k 能被树上所有点到达，要求 k 没有出边，且树上其它点都要有出边。数树上没有出边的点的数量，记录一下它的编号，如果数量为 1，且这个点编号为 k，那 k 就合法。

我们需要维护树上没有出边的点的数量、编号。指定以 1 为根，把边分为和儿子之间的、和父亲之间的，记 g_u 为 u 的儿子个数，设 c_u 表示 u 向子节点指向的出边数，b_u 表示 u 向父亲指向的出边数。则 u 没有出边就是 c_u=0 且 b_u=0。注意特判没有父亲的根节点 1。

考虑题目每个操作，对 c_u 和 b_u 的影响。操作 1 将 b_x 翻转，c_y 加 1 或减 1（x 是 y 的儿子），操作 2 令 u 所有子节点 b_v\gets 0，u 自身向儿子的出边数 c'_u=g_u，操作 3 令 u 所有子节点 b_v\gets 1，c'_u=0，操作 4 令 u 所有子节点 b_v 翻转，c'_u=g_u-c_u。

为了每个点的子节点对应一段连续区间，可以先 BFS 把点编号放上线段树。线段树上维护：

只有个数为 1 时才可能用到编号去核对 k，为了方便，可以用异或的方式维护编号，这样区间翻转 b 时直接异或过去。

时间复杂度 O(q\log n)。 ::::info[代码]

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=1e6+10;
int n,K,Q,op,x,y;
vector<pair<int,int> >v[N];
int dfu,id[N],bel[N],fa[N];
int c[N],b[N],lx[N],rx[N],gs[N];
void bfs(){
    queue<int>q;
    q.push(1);
    while(!q.empty()){
        int u=q.front();q.pop();
        lx[u]=dfu+1;
        for(auto e:v[u]){
            int to=e.first;
            if(!id[to]&&to!=fa[u]){
                id[to]=++dfu,fa[to]=u,q.push(bel[dfu]=to);
                c[u]+=e.second,b[to]=1-e.second;
            }
        }
        rx[u]=dfu,gs[u]=rx[u]-lx[u]+1;
    }
}
struct tree{
    #define mid ((l+r)>>1)
    struct node{
        int cnt,cntz,cx,zx,tag;
    }tr[N*4];
    //区间指向子节点边数为0的 cnt，区间出度为0的 cntz 
    void pushup(int id){
        tr[id].cnt=tr[id*2].cnt+tr[id*2+1].cnt;
        tr[id].cntz=tr[id*2].cntz+tr[id*2+1].cntz;
        tr[id].cx=tr[id*2].cx^tr[id*2+1].cx;
        tr[id].zx=tr[id*2].zx^tr[id*2+1].zx;
    } 
    void build(int id,int l,int r){
        if(l==r){
            tr[id]={!c[bel[l]],!b[bel[l]]&&!c[bel[l]],0,0,0};
            if(tr[id].cnt) tr[id].cx=bel[l];
            if(tr[id].cntz) tr[id].zx=bel[l];
            tr[id].tag=1+b[bel[l]];
            return ;
        }
        build(id*2,l,mid);
        build(id*2+1,mid+1,r);
        pushup(id);
    }
    void adt(int id,int op){
        if(op==1){//b赋0 
            tr[id].cntz=tr[id].cnt;
            tr[id].zx=tr[id].cx;
            tr[id].tag=1;
        }
        if(op==2){//b赋1 
            tr[id].cntz=tr[id].zx=0;
            tr[id].tag=2;
        }
        if(op==3){//b翻转 
            tr[id].cntz=tr[id].cnt-tr[id].cntz;
            tr[id].zx^=tr[id].cx;
            int &tg=tr[id].tag;
            tg=(tg==1?2:(tg==2?1:(tg^3)));
        }
    }
    void pushdown(int id){
        if(tr[id].tag){
            int &tg=tr[id].tag;
            adt(id*2,tg),adt(id*2+1,tg),tg=0;
        }
    }
    void cover(int id,int l,int r,int x,int y,int op){
        if(x<=l&&r<=y){adt(id,op);return ;}
        pushdown(id);
        if(x<=mid) cover(id*2,l,mid,x,y,op);
        if(mid+1<=y) cover(id*2+1,mid+1,r,x,y,op);
        pushup(id);
    }
    //op=-1不改父边，op=0/1赋值，op=2翻转 
    int point(int id,int l,int r,int p,int z,int op){
        if(l==r){
            int pre=tr[id].tag-1;
            int nw=(op==-1?pre:(op==2?1-pre:op));
            tr[id]={z,nw?0:z,z?bel[l]:0,(!nw&&z)?bel[l]:0,0};
            tr[id].tag=nw+1;
            return pre;
        }
        pushdown(id);
        int te;
        if(p<=mid) te=point(id*2,l,mid,p,z,op);
        else te=point(id*2+1,mid+1,r,p,z,op);
        pushup(id);
        return te;
    }
}T;
void mdf(int x){
    if(x!=1) T.point(1,1,n-1,id[x],c[x]==0,-1);
}
void change(int x,int op){//修改x的父边 
    int pre=T.point(1,1,n-1,id[x],c[x]==0,op);
    int nw=(op==2?1-pre:op);
    if(pre!=nw){
        int tc=c[fa[x]];
        c[fa[x]]+=pre-nw;
        if((tc==0)!=(c[fa[x]]==0)) mdf(fa[x]);
    }
}
void answer(){
    int cnt=T.tr[1].cntz+(c[1]==0);
    int x=T.tr[1].zx^(c[1]==0);
    //cout<<"?"<<cnt<<" "<<x<<"  ";
    if(cnt==1&&x==K) printf("YES\n");
    else printf("NO\n");
}
int main(){
    scanf("%d%d%d",&n,&K,&Q);
    for(int i=1;i<n;i++){
        scanf("%d%d",&x,&y);
        v[x].push_back({y,1});
        v[y].push_back({x,0});
    }
    bfs();
    T.build(1,1,n-1);
    answer();
    while(Q--){
        scanf("%d",&op);
        if(op==5) scanf("%d",&K);
        else{
            scanf("%d",&x);
            if(op==1){
                scanf("%d",&y);
                change((fa[x]==y?x:y),2);
            }
            else{
                int pre=c[x];
                if(lx[x]<=rx[x]) T.cover(1,1,n-1,lx[x],rx[x],op-1);
                c[x]=(op==2?gs[x]:(op==3?0:gs[x]-pre));
                if(x!=1) change(x,(op==2?1:(op==3?0:2)));
            }
        }
        answer();
    }
    return 0;
}

::::