[ sphere online judge ] SPOJ QTREE - Query on a tree 使用 link-cut tree

題目:
http://www.spoj.com/problems/QTREE/

解法:
這題可以用除了link-cut tree以外的方法來做，速度也會比較快，但是最近在研究link-cut tree，所以就試著用link-cut tree解了。
首先，對於題目給的樹，利用BFS將每個點設成單獨一個樹鏈(之後再access操作的時候就會連起來了，不用擔心)，並每個點都記錄連到父母那條邊的權重，用edge_node陣列記錄每條邊被記錄在哪個點內。因為每個點是紀錄連到父母節點邊的權重，所以不可以有換根的情形發生。修改邊時利用edge_node陣列把要修改的點找出來然後直接修改，查詢則在access的過程中完成。
記住這題node不可以用vector來做，會TLE不知道為什麼

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

#include<bits/stdc++.h> using namespace std; struct splay_tree{ int ch[2],pa; int data,ma; splay_tree():pa(0),data(0x80000000),ma(0x80000000){ch[0]=ch[1]=0;} }node[10005]; 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].ma=node[x].data; if(node[x].ch[0])node[x].ma=max(node[node[x].ch[0]].ma,node[x].ma); if(node[x].ch[1])node[x].ma=max(node[node[x].ch[1]].ma,node[x].ma); } 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 void access(int x,bool is){ int last=0; while(x){ splay(x); if(!node[x].pa&&is){ printf("%d\n",max(node[last].ma,node[node[x].ch[1]].ma)); } node[x].ch[1]=last; up(x); last=x; x=node[x].pa; } } struct EDGE{ int a,b,c; }e[10005]; int n; vector<pair<int ,int > >G[10005]; int pa[10005],edge_node[10005]; inline void bfs(int root){ std::queue<int > q; for(int i=1;i<=n;++i)pa[i]=0; q.push(root); while(q.size()){ int u=q.front(); q.pop(); for(int i=0;i<(int)G[u].size();++i){ int v=G[u][i].first; if(v!=pa[u]){ pa[v]=u; node[v].pa=u; node[v].data=e[G[u][i].second].c; edge_node[G[u][i].second]=v; up(v); q.push(v); } } } } char s[10]; int t,a,b; int main(){ scanf("%d",&t); while(t--){ scanf("%d",&n); for(int i=1;i<=n;++i){ G[i].clear(); node[i].ch[0]=node[i].ch[1]=node[i].pa=0; node[i].data=node[i].ma=0x80000000; } for(int i=1;i<n;++i){ scanf("%d%d%d",&e[i].a,&e[i].b,&e[i].c); G[e[i].a].push_back(make_pair(e[i].b,i)); G[e[i].b].push_back(make_pair(e[i].a,i)); } bfs(1); while(scanf("%s",s)&&s[0]!='D'){ scanf("%d%d",&a,&b); if(s[0]=='C'){ a=edge_node[a]; splay(a); node[a].data=b; up(a); }else{ access(a,0); access(b,1); } } } return 0; }