题意：
给出n个节点 及其父亲 和m个指令1：表示求节点i到根节点（n+1）的距离2：表示将节点i的父亲更换为j
题解：
动态树link、cut、access模板题 貌似没什么难度- -
代码：
1 #include <cstdio> 2 struct info{ 3 int fat,root,lc,rc,num; 4 info(const int a=0,const int b=1,const int c=0,const int d=0,const int e=1): 5 fat(a),root(b),lc(c),rc(d),num(e){} 6 }; 7 int n,m; 8 info tree[200002]; 9 void clean(){ 10 tree[0]=info(0,0,0,0,0); 11 } 12 void makenum(int t){ 13 tree[t].num=1+tree[tree[t].lc].num+tree[tree[t].rc].num; 14 } 15 void left(int t){ 16 int fa=tree[t].fat,r=tree[t].rc; 17 tree[t].rc=tree[r].lc; 18 tree[tree[r].lc].fat=t; 19 tree[r].lc=t; 20 tree[t].fat=r; 21 if (tree[t].root){ 22 tree[t].root=0; 23 tree[r].root=1; 24 }else if (tree[fa].lc==t) tree[fa].lc=r; 25 else tree[fa].rc=r; 26 tree[r].fat=fa; 27 clean(); 28 makenum(t); 29 makenum(r); 30 } 31 void right(int t){ 32 int fa=tree[t].fat,l=tree[t].lc; 33 tree[t].lc=tree[l].rc; 34 tree[tree[l].rc].fat=t; 35 tree[l].rc=t; 36 tree[t].fat=l; 37 if (tree[t].root){ 38 tree[t].root=0; 39 tree[l].root=1; 40 }else if (tree[fa].lc==t) tree[fa].lc=l; 41 else tree[fa].rc=l; 42 tree[l].fat=fa; 43 clean(); 44 makenum(t); 45 makenum(l); 46 } 47 void splay(int t){ 48 while (!tree[t].root){ 49 int fa=tree[t].fat,gr=tree[fa].fat; 50 if (tree[fa].root){ 51 if (tree[fa].lc==t) right(fa); 52 else left(fa); 53 }else if (tree[gr].lc==fa){ 54 if (tree[fa].lc==t) right(gr),right(fa); 55 else left(fa),right(gr); 56 }else if (tree[fa].rc==t) left(gr),left(fa); 57 else right(fa),left(gr); 58 } 59 } 60 void access(int x){ 61 int y=x; 62 x=0; 63 do{ 64 splay(y); 65 tree[tree[y].rc].root=1; 66 tree[y].rc=x; 67 tree[x].root=0; 68 clean(); 69 makenum(y); 70 x=y; 71 y=tree[x].fat; 72 }while (y); 73 } 74 void change(int x,int y){ 75 access(x); 76 splay(x); 77 tree[tree[x].lc].fat=0; 78 tree[tree[x].lc].root=1; 79 tree[x].lc=0; 80 tree[x].fat=y; 81 clean(); 82 access(x); 83 } 84 int main(){ 85 freopen("bz2002.in","r",stdin); 86 freopen("bz2002.out","w",stdout); 87 int i,x,y,z; 88 scanf("%d\n",&n); 89 for (i=1;i<=n;i++){ 90 scanf("%d",&x); 91 x+=i; 92 if (x<=n) tree[i].fat=x; 93 else tree[i].fat=n+1; 94 } 95 scanf("%d\n",&m); 96 for (i=1;i<=m;i++){ 97 scanf("%d%d",&x,&y); 98 ++y; 99 if (x==2){ 100 scanf("%d",&z); 101 change(y,y+z); 102 }else{ 103 access(y); 104 splay(y); 105 printf("%d\n",tree[tree[y].lc].num); 106 } 107 } 108 fclose(stdin); 109 fclose(stdout); 110 } View Code
转载于:https://www.cnblogs.com/g-word/p/3691741.html
相关资源：JAVA上百实例源码以及开源项目