神TM动态点分治。。
然而st表又双叒叕TM挂了 sbyzh
#include<cstdio> #include<iostream> #include<cstring> #include<cstdlib> #include<algorithm> #include<cmath> #include<queue> using namespace std; int n; struct node { int x,y,next; }a[210000];int len,last[110000]; void ins(int x,int y) { len++; a[len].x=x;a[len].y=y; a[len].next=last[x];last[x]=len; } int z,ys[110000],dep[110000]; int f[30][210000]; void dfs(int x,int fr) { f[0][++z]=dep[x];ys[x]=z; for(int k=last[x];k;k=a[k].next) { int y=a[k].y; if(y!=fr) { dep[y]=dep[x]+1; dfs(y,x); f[0][++z]=dep[x]; } } } int Bin[30],Log[210000]; void get_st() { Bin[0]=1;for(int i=1;i<=25;i++)Bin[i]=Bin[i-1]*2; Log[1]=0;for(int i=2;i<=z ;i++)Log[i]=Log[i/2]+1; for(int j=1;Bin[j]<=z;j++) for(int i=1;i+Bin[j]-1<=z;i++) f[j][i]=min(f[j-1][i],f[j-1][i+Bin[j-1]]); } int RMQ(int x,int y) { x=ys[x],y=ys[y]; if(x>y)swap(x,y); int k=Log[y-x+1]; return min(f[k][x],f[k][y-Bin[k]+1]); } //-----------get_st---------------------用于求LCA的dep int rt,sum;bool v[110000]; int tot[110000],g[110000]; void getrt(int x,int fr) { tot[x]=1,g[x]=0; for(int k=last[x];k;k=a[k].next) { int y=a[k].y; if(y!=fr&&v[y]==false) { getrt(y,x); tot[x]+=tot[y]; g[x]=max(g[x],tot[y]); } } if(fr!=0)g[x]=max(g[x],sum-tot[x]); if(g[x]<g[rt]||rt==0)rt=x; } int fa[110000]; void divi(int x) { v[x]=true; for(int k=last[x];k;k=a[k].next) { int y=a[k].y; if(v[y]==false) { sum=tot[y],rt=0; getrt(y,x),fa[rt]=x; divi(rt); } } } //------------composition----------------- struct heap //为了支持删除，开两个堆 { priority_queue<int> ha,hb; void ins(int x){ha.push(x);} void del(int x){hb.push(x);} int size(){return ha.size()-hb.size();} int top() { while(hb.size()>0&&ha.top()==hb.top()) ha.pop(), hb.pop(); if(ha.size()==0)return 0; return ha.top(); } void pop() { while(hb.size()>0&&ha.top()==hb.top()) ha.pop(), hb.pop(); ha.pop(); } int stop() { int x=top(); if(size()<=1)return 0; pop(); int y=top(); ins(x); return y; } }A,B[110000],C[110000]; //~~~init~~~ int getdis(int x,int y){return dep[x]+dep[y]-2*RMQ(x,y);} void turn_off(int f,int x) { if(f==x) { B[f].ins(0); if(B[f].size()==2) A.ins(B[f].top()); } int ff=fa[f];if(ff==0)return ; int dis=getdis(ff,x),mmax=C[f].top(); C[f].ins(dis);//upd C if(dis>mmax) { int d1=B[ff].top()+B[ff].stop(),s1=B[ff].size(); if(mmax!=0)B[ff].del(mmax); B[ff].ins(dis);//upd B int d2=B[ff].top()+B[ff].stop(),s2=B[ff].size(); if(d1<d2)//upd A { if(s1>=2)A.del(d1); if(s2>=2)A.ins(d2); } } turn_off(ff,x); } void turn_on(int f,int x) { if(f==x) { if(B[f].size()==2) A.del(B[f].top()); B[x].del(0); } int ff=fa[f];if(ff==0)return ; int dis=getdis(ff,x),mmax=C[f].top(); C[f].del(dis);//upd C if(dis==mmax) { int d1=B[ff].top()+B[ff].stop(),s1=B[ff].size(); B[ff].del(dis); if(C[f].top()!=0)B[ff].ins(C[f].top());//upd B int d2=B[ff].top()+B[ff].stop(),s2=B[ff].size();//upd C if(d1>d2) { if(s1>=2)A.del(d1); if(s2>=2)A.ins(d2); } } turn_on(ff,x); } //-----------let make it--------------------- int cc;bool col[110000]; char ss[10]; int main() { freopen("hide.in","r",stdin); freopen("hide.out","w",stdout); int x,y; scanf("%d",&n); len=0;memset(last,0,sizeof(last)); for(int i=1;i<n;i++) { scanf("%d%d",&x,&y); ins(x,y);ins(y,x); } dep[1]=0;dfs(1,0); get_st(); sum=n,rt=0; getrt(1,0),fa[rt]=0; divi(rt); cc=0; for(int i=1;i<=n;i++) cc++, col[i]=false, turn_off(i,i); int m; scanf("%d",&m); while(m--) { scanf("%s",ss+1); if(ss[1]=='G') { if(cc==0)printf("-1 "); else if(cc==1)printf("0 "); else printf("%d ",A.top()); } else { scanf("%d",&x); if(col[x]==false) cc--, col[x]=true, turn_on(x,x); else cc++, col[x]=false, turn_off(x,x); } } return 0; }