2014
01-26

# Box

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.

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.

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.

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

1
1
2

1
1

不错的一道题， 自己怎么也写不出来， 于是去问了风神。 把每个箱子看成一个括号， 箱子a在箱子b里面， 就是括号b在括号a里面。

0 1 就变成了

(  (  )  )

1 2 4 3

0 6 4 6 1 0就变成了

(  (    )  )     (  (  )   (  (  )   )   )

1 5 11 7    6 2 8 4 3 9 10 12

#include <cstdio>
#include <cstdlib>
#include <cstring>

using namespace std;

const int N = 50007;

int size, head[N], n;
int pr[N], next[N], in[N];
struct Edge
{
int v, next;

void ini(int a, int b)
{
v = b;
next = head[a];
head[a] = size++;
}
};
Edge edge[N];
int ch[N << 1][2], fa[N << 1];

void build(int x) //建树（size 表示最后加进来的节点）
{
fa[x] = size;
ch[size][1] = x;
size = x;
for(int i = head[x]; i != -1; i = edge[i].next)
{
int v = edge[i].v;
build(v);
}
fa[x + n] = size;
ch[size][1] = x + n;
size = x + n;
}

void init()
{
memset(ch, 0, sizeof(ch));
for(int i = next[0]; i != -1; i = next[i])
{
size = 0;
build(i);
}
}

inline void rotate(int x, bool f)
{
int y = fa[x];
int z = fa[y];
ch[y][!f] = ch[x][f];
fa[ch[x][f]] = y;
fa[x] = z;
if(z)
ch[z][ch[z][1] == y] = x;
ch[x][f] = y;
fa[y] = x;
}

void splay(int x, int g)
{
int y = fa[x];
while(y != g)
{
int z = fa[y];
bool f = (ch[y][0] == x);
if(z != g && f == (ch[z][0] == y))
rotate(y, f);
rotate(x, f);
y = fa[x];
}
}

void move(int a, int b)
{
if(a == b)
return ;
splay(a, 0);
splay(a + n, a);
for(int i = b; i; i = fa[i]) //判断b是否为a的孩子
if(ch[a + n][0] == i)
return ;
int x, y;
x = ch[a][0];
y = ch[a + n][1];
ch[a][0] = ch[a + n][1] = fa[x] = fa[y] = 0; //把[a, a + n]取出来
if(x && y)
{
while(ch[y][0])
y = ch[y][0];
ch[y][0] = x;
fa[x] = y;
}
if(b == 0) //[a, a + n]已经独立为一棵树了
return ;
splay(b, 0);
int i;
for(i = ch[b][1]; ch[i][0]; i = ch[i][0]) ; //找b后面的一个节点
splay(i, b);
ch[i][0] = a;
fa[a] = i;
}

int que(int a)
{
splay(a, 0); //把a移动到根，方便找这棵树的最小值
for(; ch[a][0]; a = ch[a][0]) ;
return a;
}

int main()
{
//freopen("in.txt", "r", stdin);
bool f = false;
while(~scanf("%d", &n))
{
if(f)
puts("");
else
f = true;
int tmp = 0;
pr[0] = next[0] = -1;
size = 0;
memset(head, -1, sizeof(head));
for(int i = 1; i <= n; i++)
{
scanf("%d", in + i);
if(in[i])
edge[size].ini(in[i], i);
else
{
next[tmp] = i;
next[i] = -1;
pr[i] = tmp;
tmp = i;
}
}
init();
int m;
scanf("%d", &m);
while(m--)
{
char s[10];
int a;
scanf("%s%d", s, &a);
if(s[0] == 'M')
{
int b;
scanf("%d", &b);
move(a, b);
}
else
printf("%d\n", que(a));
}
}
return 0;
}