POJ-1988 Cube Stacking

题目链接：http://poj.org/problem?id=1988

题目大意：

给你编号从1到30000的大小相同的立方体，现在我有2种操作：

1.move 1,3表示把1放在3的上面。

还有一种情况是：假如1的下面还有一个2,3的下面还有一个4，那么move1,3的意思就是把1所在的全部立方体放在3全部立方体的上面，而且保持原来1和3所在堆的立方体的顺序。移动后从上到下依次为1,2,3,4.且只能是这一种情况

2.count 3 表示询问3下面有几个立方体

解题思路：

首先我们考虑它们摞在一起后顺序不能变，只能整体移动，要询问的是下面的立方体的个数。类似询问根结点下面子结点的个数，所以我们可以考虑使用并查集来解决这道题，所以我们要用到pre数组和son数组，表示结点的父节点和这个结点的子结点总数，每次移动时，我们可以通过一次遍历，找到放在上面的全部结点，然后全部加上要放的那个堆的立方体的个数，当我们询问的时候，只需要输出这个结点的子结点的个数-1就行了（不包括本身）。

但是，做完后悲剧的发现超时了，因为数据范围太大，每次移动都需要遍历全部立方体（题目没有给立方体的个数，编号也是随机的，所以只能全部遍历）。这样很容易就TLE了。然后参考了网上的思路。。。。。。

说的是可以新开一个数组deep，表示这个结点离根结点的距离，每次移动的时候，只需要更新一次要放上去的立方体的个数，就是移动后该结点到根结点的距离。查询的时候，只需要用总数-离根结点的距离然后-1就可以求出这个结点下面的立方体的个数了。非常巧妙，ym！~~~~~~~~~~~~

然后通过这道题，对递归又有了一点的认识，在递归过程中，每个语句顺序都不能随便改变，因为递归一次，它就可能使用，使用之后值就会发生改变，而这些改变可能是递归多次后发生的，非常不容易察觉。。。所以递归的时候一定要注意！~~这个地方郁闷了半个小时。。。

代码如下：

#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;
#define N 30010
int pre[N], son[N], deep[N];

int find(int x)
{
	int temp;
	if(x == pre[x])
		return x;
	temp = pre[x];	
	pre[x] = find(temp);
	deep[x] += deep[temp]; //与根结点的距离
	return pre[x];
}

int main()
{
	int p;
	char ope;
	int a, b;
	int query;
	int root1, root2;
	scanf("%d", &p);
	for(int i = 1; i < N; ++i) //init
	{
		pre[i] = i;
		son[i] = 1;
		deep[i] = 0;
	}
	for(int i = 0; i < p; ++i)
	{
		scanf("%*c%c", &ope);
		if(ope == 'M')
		{
			scanf("%d%d", &a, &b);
			root1 = find(a);
			root2 = find(b);
			if(root1 != root2)
			{
				pre[root2] = root1;
				deep[root2] = son[root1]; //更新深度
				son[root1] += son[root2]; //更新结点数
			}
		}
		else
		{
			scanf("%d", &query);
			printf("%d\n", son[find(query)] - deep[query] - 1); //-1不包括本身
		}
	}
	return 0;
}