B - Query on a tree again!

Query on a tree again!

#include<iostream>
#include<cstring>
#include<cmath>
#include<stdlib.h>
#include<cstdio>
# define PI 3.14159265358979323846
#define qc std::ios::sync_with_stdio(false)
using namespace std;
const int maxl=300100;
const int minl=-217483648;
const int mod=1000000;
int n,m,q;
struct edge{
    int to,next;
    edge(){
        to=next=0;
    }
};
struct node
{
    bool z;
    int v,depth,son,zson;
    int pre;//对应重链序的下表
    int top;//头结点位置
    int fa;//父节点
    node(){
        z=false;
        v=0,depth=0,son=0;
        pre=0;
    }
};
struct zro{
    static int cnt;
    static int ni;
    static bool debug_is_off;
    zro(){
        cnt=0;
        ni=0;
        debug_is_off=false;
    }
};
struct seg_t
{
    int r,l,mid;
    int left;
    int v;
};
int zro::cnt=0;
int zro::ni=0;
bool zro::debug_is_off=false;
edge e[maxl<<1]; zro zr;
node n_[maxl<<1];
seg_t tree[maxl<<2];
int v[maxl<<1], head[maxl<<1],ys[maxl<<1];
void addedge(int u,int v){
    e[++zr.cnt].next=head[u];
    e[zr.cnt].to=v;
    head[u]=zr.cnt;
}
void dfs1(int node,int depth,int f){
    int son=0,ma=0,mi=0;
    n_[node].depth=depth;
    for(int i=head[node];i!=0;i=e[i].next){
        if(e[i].to==f)continue;
        dfs1(e[i].to,depth+1,node);
        son+=n_[e[i].to].son+1;
        if(n_[e[i].to].son>=ma){
            ma=n_[e[i].to].son,mi=e[i].to;
        }
    }
    n_[mi].z=true;
    n_[node].zson=mi;
    n_[node].son=son;
    n_[node].fa=f;
}
void dfs2(int node,int top){
    ys[++zr.ni]=node;
    n_[node].pre=zr.ni;
    int z=n_[node].zson;
    if(node==1)n_[node].top=node;
    else if(n_[node].z)n_[node].top=n_[n_[node].fa].top;
    else n_[node].top=node;
    if(z)dfs2(z,node);
    for(int i=head[node];i!=0;i=e[i].next){
        if(e[i].to==n_[node].fa||n_[e[i].to].z)continue;
        dfs2(e[i].to,node);
    }
}
void pushup(int k){
    tree[k].left=min(tree[k<<1].left,tree[k<<1|1].left);
    tree[k].v=tree[k<<1].v+tree[k<<1|1].v;
}
void build(int k,int l,int r){
    tree[k].l=l;tree[k].r=r;
    if(l==r)
    {   
        tree[k].left=maxl;
        tree[k].v=n_[ys[l]].v;
        return;
    }
    int mid=(l+r)>>1;
    build(k<<1,l,mid);build(k<<1|1,mid+1,r);
    pushup(k);
}

void tree_update(int k,int index){
    if(tree[k].r==tree[k].l){
        tree[k].v^=1;
        if(tree[k].v){
            tree[k].left=index;
        //  cout<<"left:  "<<index<<endl;
        }
        else tree[k].left=maxl;
        n_[ys[index]].v^=1;
        return;
    }
    int mid=(tree[k].l+tree[k].r)>>1;
    if(index<=mid)tree_update(k<<1,index);
    if(index>mid)tree_update(k<<1|1,index);
    pushup(k);
}
int tree_left(int k,int l,int r){
    if(tree[k].l>=l&&tree[k].r<=r){
        return tree[k].left;
    }
    int mid=(tree[k].l+tree[k].r)>>1;
    int left=maxl;
    if(l<=mid)left=min(left,tree_left(k<<1,l,r));
    if(r>mid)left=min(left,tree_left(k<<1|1,l,r));
    return left;
}
int find_left(int l,int r){
    int maxnum=maxl;
    if(n_[l].top==n_[r].top)maxnum= tree_left(1,min(n_[l].pre,n_[r].pre),max(n_[l].pre,n_[r].pre));
    else if(n_[n_[l].top].depth>=n_[n_[r].top].depth){
        maxnum= min(find_left(l,n_[l].top),find_left(n_[n_[l].top].fa,r));
    }
    else{
        maxnum= min(find_left(r,n_[r].top),find_left(l,n_[n_[r].top].fa));
    }
    return maxnum;
}
void update(int index,int v){
    int in=n_[index].pre;
    tree_update(1,in);
}
void init(){
    memset(e,0,sizeof(e));
    memset(n_,0,sizeof(n));
    memset(tree,0,sizeof(tree));
    memset(v,0,sizeof(v));
    memset(head,0,sizeof(head));
    memset(ys,0,sizeof(ys));
    zr.cnt=0;
    zr.ni=0;
}
int main(){
    //qc;
        while(cin>>n>>q){
            init();
        for(int i=1;i<n;i++){
            int a,b;
            scanf("%d%d",&a,&b);
            addedge(a,b);
            addedge(b,a);
        }
        for(int i=1;i<=n;i++){
            n_[i].v=0;
        }
        dfs1(1,1,0);
        dfs2(1,0);
        build(1,1,zr.ni);
        
        for(int i=1;i<=q;i++){
            int a,b;
            scanf("%d%d",&a,&b);
            if(a==0)update(b,b);
            else if(a==1){
                int ans=find_left(1,b);
                if(ans!=maxl)printf("%d\n",ys[ans]);
                else printf("-1\n");
            }
        }
        }
    /*
8
1 2 1 3
2 4 2 5
3 6 3 7
4 8
1 2 3 4 5 6 7 8
     */
    
    
}