[ 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; }

[ zerojudge ] b483:史蒂芙的觀察日記 (link cut tree)

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

解法:
動態加邊的最小生成森林
每增加一條邊後，如果產生環，可以利用迴路性質將環上的最大邊刪除，這個操作可以用link cut tree完成，因為link cut tree無法維護邊權，所以我們把邊轉化成點，也就是在兩個點之間的邊改成一個點，分別連到這兩個點，而他的權重就是邊的權重，類似於這樣:
u-v -> u-k-v，k存的是uv邊的邊權
如此一來只要想辦法維護好原來的那些點權讓他們不會影響到邊權即可

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 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125

#include<bits/stdc++.h> #define MAXN 200005 using namespace std; struct edge{ int s,t,w; }e[MAXN/2]; struct splay_tree{ int pa,ch[2]; bool rev; int ma; splay_tree():pa(0),rev(0),ma(0){ch[0]=ch[1]=0;} }node[MAXN]; int v[MAXN]; int n,m; 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){ int lc=node[x].ch[0],rc=node[x].ch[1]; node[x].ma=(v[node[lc].ma]>v[node[rc].ma])?node[lc].ma:node[rc].ma; node[x].ma=v[x]>v[node[x].ma]?x:node[x].ma; } inline void down(int x){ if(node[x].rev){ if(node[x].ch[0])node[node[x].ch[0]].rev^=1; if(node[x].ch[1])node[node[x].ch[1]].rev^=1; std::swap(node[x].ch[0],node[x].ch[1]); node[x].rev^=1; } } void push_down(int x){ if(!isroot(x))push_down(node[x].pa); down(x); } 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){ push_down(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 make_root(int x){ access(x),splay(x); node[x].rev^=1; } inline void add(int x){ int s=e[x].s,t=e[x].t; make_root(t),node[t].pa=x+n; node[x+n].pa=s; v[x+n]=e[x].w; node[x+n].ma=x+n; } inline void del(int x){ int u=e[x].s,v=e[x].t; make_root(u); access(v),splay(v); node[v].ch[0]=0; node[v].ma=node[u].ma=0; node[u].pa=node[x+n].pa=0; node[u].ch[1]=0; } inline int find_root(int x){ x=access(x); while(node[x].ch[0])x=node[x].ch[0]; splay(x); return x; } int ans; inline void insert(int x){ int u=e[x].s,v=e[x].t,w=e[x].w; if(find_root(u)!=find_root(v))add(x),ans+=w; else{ make_root(u),access(v),splay(v); if(e[node[v].ma-n].w>w){ ans-=e[node[v].ma-n].w; del(node[v].ma-n); ans+=w; add(x); } } } int main(){ for(int cnt=1;~scanf("%d%d",&n,&m);++cnt){ printf("Case #%d\n",cnt); for(int i=0;i<n+m+1;++i){ node[i].ch[0]=node[i].ch[1]=0; node[i].ma=node[i].pa=0; node[i].rev=0; v[i]=0; } ans=0; for(int i=1;i<=m;++i){ scanf("%d%d%d",&e[i].s,&e[i].t,&e[i].w); insert(i); printf("%d\n",ans); } } return 0; }