你们搞的这个题目啊，exciting！……
LCT裸题嘛。记得特判一下根节点所连出的边是否会成环就行了，还有删边的时候特判一下是否需要把这条边加回去。
几天不写LCT，结果一写就写出各种脑残错误，我怎么这么菜，233……
1 #include<cstdio> 2 #include<cstring> 3 #include<algorithm> 4 #define isroot(x) ((x)->p==null||((x)->p->ch[0]!=(x)&&(x)->p->ch[1]!=(x))) 5 #define dir(x) ((x)==(x)->p->ch[1]) 6 using namespace std; 7 const int maxn=200010; 8 struct node{ 9 int size; 10 node *ch[2],*p,*go; 11 node():size(1){} 12 inline void refresh(){size=ch[0]->size+ch[1]->size+1;} 13 }null[maxn]; 14 void newnode(node*); 15 node *access(node*); 16 void link(node*,node*); 17 void cut(node*); 18 node *getroot(node*); 19 void splay(node*); 20 void rot(node*,int); 21 int n,m,a[maxn],d,x; 22 int main(){ 23 newnode(null); 24 null->size=0; 25 scanf("%d%d",&n,&m); 26 for(int i=1;i<=n;i++)newnode(null+i); 27 for(int i=1;i<=n;i++){ 28 scanf("%d",&a[i]); 29 if(i+a[i]>0&&i+a[i]<=n)link(null+i,null+i+a[i]); 30 } 31 while(m--){ 32 scanf("%d%d",&d,&x); 33 if(d==1){ 34 node *y=getroot(null+x); 35 if(y->go!=null)printf("-1 "); 36 else printf("%d ",y->size); 37 } 38 else{ 39 cut(null+x); 40 scanf("%d",&a[x]); 41 if(x+a[x]>0&&x+a[x]<=n)link(null+x,null+x+a[x]); 42 } 43 } 44 return 0; 45 } 46 inline void newnode(node *x){x->ch[0]=x->ch[1]=x->p=x->go=null;} 47 node *access(node *x){ 48 node *y=null; 49 while(x!=null){ 50 splay(x); 51 x->ch[1]=y; 52 (y=x)->refresh(); 53 x=x->p; 54 } 55 return y; 56 } 57 void link(node *x,node *y){//此时x一定是所在树的根 58 if(getroot(y)==x)x->go=y; 59 else{ 60 splay(x); 61 x->p=y; 62 } 63 } 64 void cut(node *x){ 65 access(x); 66 splay(x); 67 if(x->ch[0]==null)x->go=null;//如果它是根，那么这个操作只可能是断掉成环的这条边 68 else{ 69 node *y=getroot(x); 70 splay(x); 71 x->ch[0]->p=null; 72 x->ch[0]=null; 73 x->refresh(); 74 if(getroot(y->go)==x){//说明它在环上 75 link(y,y->go); 76 y->go=null; 77 } 78 } 79 } 80 node *getroot(node *x){ 81 x=access(x); 82 while(x->ch[0]!=null)x=x->ch[0]; 83 splay(x); 84 return x; 85 } 86 void splay(node *x){ 87 while(!isroot(x)){ 88 if(isroot(x->p)){ 89 rot(x->p,dir(x)^1); 90 break; 91 } 92 if(dir(x)==dir(x->p))rot(x->p->p,dir(x->p)^1); 93 else rot(x->p,dir(x)^1); 94 rot(x->p,dir(x)^1); 95 } 96 } 97 void rot(node *x,int d){ 98 node *y=x->ch[d^1]; 99 if((x->ch[d^1]=y->ch[d])!=null)y->ch[d]->p=x; 100 y->p=x->p; 101 if(!isroot(x))x->p->ch[dir(x)]=y; 102 (y->ch[d]=x)->p=y; 103 x->refresh(); 104 y->refresh(); 105 }
大力踩了一发标程，哈哈……(装B
我能说这题我早就想出出来了嘛……真是尴尬= =
看你们这么会玩，我也想在bzoj上出题了233……(这货肯定会出毒瘤题报复社会……