[ zerojudge ] b487:變態史考古錯誤報導篇 (link cut tree)

題目:
http://zerojudge.tw/ShowProblem?problemid=b487
http://zerojudge.tw/ShowProblem?problemid=b486

解法:
本題的code也可以AC b486:變態史考古
link cut tree的基本操作加上維護子樹大小即可，注意的是本題不需要用到make_root的操作，每次的cut_parents()都會保證切下來的點是其子樹的根，所以將rev、down()、push_down()刪除可減少執行時間及記憶體。

code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90

#include<bits/stdc++.h> using namespace std; struct splay_tree{ int ch[2],pa; int s; splay_tree():pa(0),s(0){ch[0]=ch[1]=0;} }node[100005]; inline bool isroot(int x){ return node[node[x].pa].ch[0]!=x&&node[node[x].pa].ch[1]!=x; } inline void up(int x){ node[x].s=node[node[x].ch[0]].s+node[node[x].ch[1]].s+1; } inline void rotate(int x){ int y=node[x].pa,z=node[y].pa,d=(node[y].ch[1]==x); node[x].pa=z; if(!isroot(y))node[z].ch[node[z].ch[1]==y]=x; node[y].ch[d]=node[x].ch[d^1]; node[node[y].ch[d]].pa=y; node[y].pa=x,node[x].ch[d^1]=y; up(y); up(x); } inline void splay(int x){ while(!isroot(x)){ int y=node[x].pa; if(!isroot(y)){ int z=node[y].pa; if((node[z].ch[0]==y)^(node[y].ch[0]==x))rotate(y); else rotate(x); } rotate(x); } } inline int access(int x){ int last=0; while(x){ splay(x); node[x].ch[1]=last; up(x); last=x; x=node[x].pa; } return last; } inline void cut_parents(int x){ access(x); splay(x); node[node[x].ch[0]].pa=0; node[x].ch[0]=0; } inline void link(int x,int y){ node[x].pa=y; } inline int find_root(int x){ x=access(x); while(node[x].ch[0])x=node[x].ch[0]; splay(x); return x; } inline int find_lca(int u,int v){ access(u); return access(v); } int n,m,x,y; int main(){ while(~scanf("%d%d",&n,&m)){ for(int i=1;i<=n;++i){ node[i].pa=node[i].ch[0]=node[i].ch[1]=0; node[i].s=0; } for(char c[5];m--;){ scanf("%s%d%d",c,&x,&y); if(c[0]=='n'){ cut_parents(x); link(x,y); }else{ if(find_root(x)!=find_root(y)){ puts("-1"); continue; } int u=node[access(find_lca(x,y))].s*2; int d=node[access(x)].s+node[access(y)].s; int g=__gcd(u,d); printf("%d/%d\n",u/g,d/g); } } } return 0; }