LCT秒天秒地
树剖比较裸的题了
用线段树记录一下区间的最左边的黑点的编号（因为同一条链上肯定是最左边的深度最小，到根节点距离最近）
然后记得树剖的时候肯定是越后面的答案越优，因为深度越浅
1 //minamoto 2 #include<bits/stdc++.h> 3 using namespace std; 4 #define getc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++) 5 char buf[1<<21],*p1=buf,*p2=buf; 6 inline int read(){ 7 #define num ch-'0' 8 char ch;bool flag=0;int res; 9 while(!isdigit(ch=getc())) 10 (ch=='-')&&(flag=true); 11 for(res=num;isdigit(ch=getc());res=res*10+num); 12 (flag)&&(res=-res); 13 #undef num 14 return res; 15 } 16 char sr[1<<21],z[20];int C=-1,Z; 17 inline void Ot(){fwrite(sr,1,C+1,stdout),C=-1;} 18 inline void print(int x){ 19 if(C>1<<20)Ot();if(x<0)sr[++C]=45,x=-x; 20 while(z[++Z]=x%10+48,x/=10); 21 while(sr[++C]=z[Z],--Z);sr[++C]=' '; 22 } 23 const int N=1e5+5; 24 int head[N],Next[N<<1],ver[N<<1],tot; 25 inline void add(int u,int v){ 26 ver[++tot]=v,Next[tot]=head[u],head[u]=tot; 27 } 28 int dfn[N],sz[N],son[N],fa[N],bl[N],val[N],top[N],cnt,n,m; 29 void dfs1(int u){ 30 sz[u]=1; 31 for(int i=head[u];i;i=Next[i]){ 32 int v=ver[i]; 33 if(v!=fa[u]){ 34 fa[v]=u,dfs1(v),sz[u]+=sz[v]; 35 if(sz[son[u]]<sz[v]) son[u]=v; 36 } 37 } 38 } 39 void dfs2(int u,int t){ 40 dfn[u]=++cnt,bl[cnt]=u,top[u]=t; 41 if(son[u]){ 42 dfs2(son[u],t); 43 for(int i=head[u];i;i=Next[i]){ 44 int v=ver[i]; 45 if(v!=fa[u]&&v!=son[u]) dfs2(v,v); 46 } 47 } 48 } 49 int mx[N<<2]; 50 #define ls (p<<1) 51 #define rs (p<<1|1) 52 inline void upd(int p){ 53 mx[p]=mx[ls]?mx[ls]:mx[rs]; 54 } 55 void build(int p,int l,int r){ 56 if(l==r) return (void)(mx[p]=val[bl[l]]?bl[l]:0); 57 int mid=(l+r)>>1; 58 build(ls,l,mid),build(rs,mid+1,r); 59 upd(p); 60 } 61 void update(int p,int l,int r,int x){ 62 if(l==r) return (void)(mx[p]=val[bl[l]]?bl[l]:0); 63 int mid=(l+r)>>1; 64 x<=mid?update(ls,l,mid,x):update(rs,mid+1,r,x); 65 upd(p); 66 } 67 int query(int p,int l,int r,int ql,int qr){ 68 if(ql<=l&&qr>=r) return mx[p]; 69 int mid=(l+r)>>1,res=0; 70 if(ql<=mid&&(res=query(ls,l,mid,ql,qr))) return res; 71 if(qr>mid&&(res=query(rs,mid+1,r,ql,qr))) return res; 72 return 0; 73 } 74 inline void change(int i){ 75 val[i]^=1,update(1,1,n,dfn[i]); 76 } 77 inline int get(int u){ 78 int res=0,p; 79 while(top[u]!=1){ 80 p=query(1,1,n,dfn[top[u]],dfn[u]); 81 p?res=p:0; 82 u=fa[top[u]]; 83 } 84 p=query(1,1,n,1,dfn[u]);p?res=p:0; 85 return res?res:-1; 86 } 87 int main(){ 88 // freopen("testdata.in","r",stdin); 89 n=read(),m=read(); 90 for(int i=1,u,v;i<n;++i) 91 u=read(),v=read(),add(u,v),add(v,u); 92 dfs1(1),dfs2(1,1),build(1,1,n); 93 while(m--){ 94 int op=read(),u=read(); 95 op&1?print(get(u)):change(u); 96 } 97 Ot(); 98 return 0; 99 }