BZOJ2002 弹飞绵羊 （LCT）

题目大意

要求维护一棵有根树，支持断开一条边并加入一条边，查询到根的距离。

---

题解

LCT维护即可，注意是有根树，link和cut之前不能move_root否则会tle。

---

代码

#include <cstdio> #include <iostream> using namespace std; const int maxn=int(2e5)+111; int n,m; int p[maxn]; struct Node { int key,siz; Node *ch[2],*fa; Node(); Node(int); int son() { if(this==fa->ch[0]) return 0; if(this==fa->ch[1]) return 1; return -1; } void maintain(); }*null,node[maxn]; Node:: Node():key(-1) { siz=null?1:0; ch[0]=ch[1]=fa=null; } Node:: Node(int _):key(_) { siz=null?1:0; ch[0]=ch[1]=fa=null; } void Node:: maintain() { siz=ch[0]->siz+1+ch[1]->siz; return; } void Rotate(Node* cur,int dir) { Node* tmp=cur->ch[dir^1]; cur->ch[dir^1]=tmp->ch[dir], tmp->ch[dir]->fa=cur; tmp->ch[dir]=cur; cur->maintain(), tmp->maintain(); if(~cur->son()) cur->fa->ch[cur->son()]=tmp; tmp->fa=cur->fa, cur->fa=tmp; return; } void Splay(Node* cur) { while(~cur->son()) { int dir=cur->son(); if(dir==cur->fa->son()) Rotate(cur->fa->fa,dir^1); Rotate(cur->fa,dir^1); } return; } void Access(Node* cur) { Node* tmp=null; while(cur!=null) { Splay(cur); cur->ch[1]=tmp, cur->maintain(); tmp=cur, cur=cur->fa; } return; } void Modify(Node* x,Node* y) { Access(x), Splay(x); x->ch[0]->fa=null; x->ch[0]=null, x->maintain(); x->fa=y; return; } void init_null() { null=new Node(-1); null->ch[0]=null->ch[1]=null->fa=null; return; } int main() { #ifndef ONLINE_JUDGE freopen("input.txt","r",stdin); freopen("output.txt","w",stdout); #endif // ONLINE_JUDGE init_null(); scanf("%d",&n); for(int i=1;i<=n;i++) { scanf("%d",&p[i]); node[i]=Node(i); if(i+p[i]<=n) node[i].fa=&node[i+p[i]]; } scanf("%d",&m); for(int i=0;i<m;i++) { int op,x,y; scanf("%d%d",&op,&x); x++; if(op==1) { Access(&node[x]); Splay(&node[x]); printf("%d\n",node[x].siz); } else { scanf("%d",&y); if(x+y<=n) Modify(&node[x],&node[x+y]); else Modify(&node[x],null); } } return 0; }