Box
Time Limit: 5000ms
Memory Limit: 32768KB
This problem will be judged on HDU. Original ID: 247564-bit integer IO format: %I64d Java class name: Main
There are N boxes on the ground, which are labeled by numbers from 1 to N. The boxes are magical, the size of each one can be enlarged or reduced arbitrarily.
Jack can perform the “MOVE x y” operation to the boxes: take out box x; if y = 0, put it on the ground; Otherwise, put it inside box y. All the boxes inside box x remain the same. It is possible that an operation is illegal, that is, if box y is contained (directly or indirectly) by box x, or if y is equal to x.
In the following picture, box 2 and 4 are directly inside box 6, box 3 is directly inside box 4, box 5 is directly inside box 1, box 1 and 6 are on the ground.
The picture below shows the state after Jack performs “MOVE 4 1”:
Then he performs “MOVE 3 0”, the state becomes:
During a sequence of MOVE operations, Jack wants to know the root box of a specified box. The root box of box x is defined as the most outside box which contains box x. In the last picture, the root box of box 5 is box 1, and box 3’s root box is itself.
Jack can perform the “MOVE x y” operation to the boxes: take out box x; if y = 0, put it on the ground; Otherwise, put it inside box y. All the boxes inside box x remain the same. It is possible that an operation is illegal, that is, if box y is contained (directly or indirectly) by box x, or if y is equal to x.
In the following picture, box 2 and 4 are directly inside box 6, box 3 is directly inside box 4, box 5 is directly inside box 1, box 1 and 6 are on the ground.
The picture below shows the state after Jack performs “MOVE 4 1”:
Then he performs “MOVE 3 0”, the state becomes:
During a sequence of MOVE operations, Jack wants to know the root box of a specified box. The root box of box x is defined as the most outside box which contains box x. In the last picture, the root box of box 5 is box 1, and box 3’s root box is itself.
Input
Input contains several test cases.
For each test case, the first line has an integer N (1 <= N <= 50000), representing the number of boxes.
Next line has N integers: a1, a2, a3, ... , aN (0 <= ai <= N), describing the initial state of the boxes. If ai is 0, box i is on the ground, it is not contained by any box; Otherwise, box i is directly inside box ai. It is guaranteed that the input state is always correct (No loop exists).
Next line has an integer M (1 <= M <= 100000), representing the number of MOVE operations and queries.
On the next M lines, each line contains a MOVE operation or a query:
1. MOVE x y, 1 <= x <= N, 0 <= y <= N, which is described above. If an operation is illegal, just ignore it.
2. QUERY x, 1 <= x <= N, output the root box of box x.
For each test case, the first line has an integer N (1 <= N <= 50000), representing the number of boxes.
Next line has N integers: a1, a2, a3, ... , aN (0 <= ai <= N), describing the initial state of the boxes. If ai is 0, box i is on the ground, it is not contained by any box; Otherwise, box i is directly inside box ai. It is guaranteed that the input state is always correct (No loop exists).
Next line has an integer M (1 <= M <= 100000), representing the number of MOVE operations and queries.
On the next M lines, each line contains a MOVE operation or a query:
1. MOVE x y, 1 <= x <= N, 0 <= y <= N, which is described above. If an operation is illegal, just ignore it.
2. QUERY x, 1 <= x <= N, output the root box of box x.
Output
For each query, output the result on a single line. Use a blank line to separate each test case.
Sample Input
2 0 1 5 QUERY 1 QUERY 2 MOVE 2 0 MOVE 1 2 QUERY 1 6 0 6 4 6 1 0 4 MOVE 4 1 QUERY 3 MOVE 1 4 QUERY 1
Sample Output
1 1 2 1 1
Source
解题：Link-Cut tree
1 #include <bits/stdc++.h> 2 using namespace std; 3 const int maxn = 300010; 4 struct LCT{ 5 int fa[maxn],ch[maxn][2],parent[maxn]; 6 void init(){ 7 memset(fa,0,sizeof fa); 8 memset(ch,0,sizeof ch); 9 } 10 void rotate(int x,int kd){ 11 int y = fa[x]; 12 ch[y][kd^1] = ch[x][kd]; 13 fa[ch[x][kd]] = y; 14 fa[x] = fa[y]; 15 ch[x][kd] = y; 16 fa[y] = x; 17 if(fa[x]) ch[fa[x]][y == ch[fa[x]][1]] = x; 18 } 19 void splay(int x,int goal = 0){ 20 int y = x; 21 while(fa[y]) y = fa[y]; 22 if(x != y){ 23 parent[x] = parent[y]; 24 parent[y] = 0; 25 while(fa[x] != goal){ 26 if(fa[fa[x]] == goal) rotate(x,x == ch[fa[x]][0]); 27 else{ 28 int y = fa[x],z = fa[y],s = (y == ch[z][0]); 29 if(x == ch[y][s]){ 30 rotate(x,s^1); 31 rotate(x,s); 32 }else{ 33 rotate(y,s); 34 rotate(x,s); 35 } 36 } 37 } 38 } 39 } 40 void access(int x){ 41 for(int y = 0; x; x = parent[x]){ 42 splay(x); 43 fa[ch[x][1]] = 0; 44 parent[ch[x][1]] = x; 45 ch[x][1] = y; 46 fa[y] = x; 47 parent[y] = 0; 48 y = x; 49 } 50 } 51 int GetRoot(int x){ 52 access(x); 53 splay(x); 54 while(ch[x][0]) x = ch[x][0]; 55 return x; 56 } 57 void cut(int x){ 58 access(x); 59 splay(x); 60 parent[ch[x][0]] = parent[x]; 61 parent[x] = 0; 62 fa[ch[x][0]] = 0; 63 ch[x][0] = 0; 64 } 65 void join(int x,int y){ 66 if(!y) cut(x); 67 else{ 68 access(y); 69 splay(y); 70 int z = x; 71 while(fa[z]) z = fa[z]; 72 if(z != y){ 73 cut(x); 74 parent[x] = y; 75 } 76 } 77 } 78 }lct; 79 int main(){ 80 int n,m,u,v; 81 char op[10]; 82 bool flag = false; 83 while(~scanf("%d",&n)){ 84 lct.init(); 85 if(flag) putchar(' '); 86 for(int i = 1; i <= n; ++i) 87 scanf("%d",&lct.parent[i]); 88 scanf("%d",&m); 89 while(m--){ 90 scanf("%s%d",op,&u); 91 if(op[0] == 'Q') printf("%d ",lct.GetRoot(u)); 92 else{ 93 scanf("%d",&v); 94 lct.join(u,v); 95 } 96 } 97 flag = true; 98 } 99 return 0; 100 }