前言
今天可以说是重新学了一下树剖吧，悄咪咪的打题，看了好久，纪念一下
题目分析
题目很简单，就是一共两种操作：
0 x把原来黑色的变成白色，白色的变成黑色1 x从 $1$ 到 $x$ 找到第一个黑子，如果没有就输出-1
操作一很简单，直接更改就行，线段树上也是单点修改，记得给节点打上标记。操作二我的思路是，从 $x$ 开始，每次向上找它所在重链头到他的区间和，借此判断上面有没有黑子，如果有就暴力从重链头开始找找到第一个出现的黑子并退出，然后再把 $x$ 变成重链头的父亲并继续循环，知道 $x$ 变成 $1$ 为止，这里要加上一个特判，就是对于 $1$ 要特判其行不行，不然会出现一种情况就是 $1$ 恰好是重链头的父亲就直接退出了，这样的话 $1$ 就会略过（这个问题看了好久，不加就只会有 $57$ 分）。
code
#include<bits/stdc++.h>
#define int long long
#define ls root<<1
#define rs root<<1|1
#define as (start+end)>>1
const int N=5000005;
using namespace std;
struct node{
int to,next;
}edge[N];
int head[N],tot;
int n,q;
int tr[N];
int dep[N],siz[N],fa[N],son[N],top[N];
int id[N],back[N],cnt;
bool be[N];
void add(int x,int y){
tot++;
edge[tot].to=y;
edge[tot].next=head[x];
head[x]=tot;
}
void dfs1(int x,int f){
dep[x]=dep[f]+1;
siz[x]=1;
fa[x]=f;
for(int i=head[x];i;i=edge[i].next){
int xx=edge[i].to;
if(xx==f) continue;
dfs1(xx,x);
siz[x]+=siz[xx];
if(!son[x] || siz[xx]>siz[son[x]]) son[x]=xx;
}
}
void dfs2(int x,int tv){
top[x]=tv;
id[x]=++cnt;
back[cnt]=x;
if(!son[x]) return ;
dfs2(son[x],tv);
for(int i=head[x];i;i=edge[i].next){
int xx=edge[i].to;
if(xx==son[x] || xx==fa[x]) continue;
dfs2(xx,xx);
}
}
void pushup(int root){
tr[root]=tr[ls]+tr[rs];
}
void updata(int root,int start,int end,int pos){
if(start==end){
tr[root]^=1;
return ;
}
int mid=as;
if(pos<=mid) updata(ls,start,mid,pos);
else updata(rs,mid+1,end,pos);
pushup(root);
}
int qurey(int root,int start,int end,int l,int r){
if(start>=l && end<=r) return tr[root];
int mid=as;
int res=0;
if(mid>=l) res+=qurey(ls,start,mid,l,r);
if(mid<r) res+=qurey(rs,mid+1,end,l,r);
return res;
}
signed main(){
cin>>n>>q;
for(int i=1;i<n;i++){
int x,y;
cin>>x>>y;
add(x,y),add(y,x);
}
dfs1(1,1);
dfs2(1,1);
while(q--){
int num,x;
cin>>num>>x;
if(num==1){
int output=-1;
int flag=0;
while(1){
int res=qurey(1,1,cnt,id[top[x]],id[x]);
if(res>=1){
flag=1;
for(int i=id[top[x]];i<=id[x];i++){
if(be[back[i]]){
output=back[i];
break;
}
}
}
x=fa[top[x]];
if(x==1){
if(be[back[x]]) output=1,flag=1;
break;
}
}
if(!flag) puts("-1");
else cout<<output<<endl;
}
else{
updata(1,1,cnt,id[x]);
be[x]^=1;
}
}
return 0;
}