hdu 3635 Dragon Balls（加权并查集）2010 ACM-ICPC Multi-University Training Contest（19）

这道题说，在很久很久以前，有一个故事。故事的名字叫龙珠。后来，龙珠不知道出了什么问题，从7个变成了n个。

在悟空所在的国家里有n个城市，每个城市有1个龙珠，第i个城市有第i个龙珠。

然后，每经过一段时间，城市i的所有的龙珠都会被转移到城市j中。

现在有两种操作：

1. T A B，表示将A龙珠所在城市的所有龙珠全部转移到B龙珠所在城市去。

2. Q A，表示询问A龙珠所在的城市X，以及X城市有几个龙珠，A龙珠被转移了几次。

输入：

第一行输入1个整型数字t，表示一共t组测试样例。

接下来，每组样例第一行包含2个整型数字n，m，表示共有n个城市，m次操作。

操作有T A B，以及Q A两种，具体含义看上面。

输出：

当输入Q A时，输出所询问的数据。每次输出占一行。

说实话，我写这道题的时候，感觉这道题相当有问题。

因为我做不出来，所以依然可耻地看了题解。但是题解中居然是用了并查集！

并查集是有问题的。因为在T A B时，它的含义是龙珠A移动到龙珠B那里，也就是说，之后的T B A 是没有意义的。但实际上，如果是按照城市A的龙珠转移到城市B去，那么实际上之后再进行T B A是有意义的。所以，是不能使用并查集的。

后来我发现我读错题了……

所以，你可以忽略以上六行的文字，包括这一行。

分析：

正确理解了题意以后，发现这是一道加权并查集。而且每个节点有两个权值。一个是所在城市的龙珠数量sum[]，一个是移动次数mv[]。

所以可以开3个数组。然后注意一下每个数据的计算方式就行了。

初始化时，每个龙珠的父节点是自己，所在城市的龙珠数量为1，移动次数为0。

接下来，每移动一次，所移动的龙珠集合的根节点的移动次数从0变成1，其它龙珠的移动次数依次变成他的父节点的移动次数+自己的移动次数，即mv[x] = mv[fx]+mv[x]（这一句不理解不要紧，自己在纸上推一下，注意路径压缩）。 而且是递归修改，从根节点开始修改，然后是以根节点为父节点的节点，然后是依次递归回溯。这样可以在我们用到某个节点的时候，一次将这个节点更新成功，而如果每次修改时都更改所有被修改的节点，那么许多节点都会被修改多次。这样，所必须的修改就是将被合并的根节点修改一次即可。

具体见代码——

#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;

const int N = 10010;

int n, m, t;
int sum[N], fm[N], mv[N];   //分别表示龙珠所在地的龙珠数量和，某龙珠的父节点，某龙珠被移动的次数
int a, b;
char s[2];

void init()
{
    scanf("%d%d", &n, &m);
    for(int i = 0; i <= n; i++)         //初始化
    {
        fm[i] = i;
        sum[i] = 1;
        mv[i] = 0;
    }
}

int mfind(int x)                        //合并与查询时都使用
{
    if(x == fm[x]) return x;
    int fx = fm[x];
    fm[x] = mfind(fm[x]);
    mv[x] += mv[fx];                    //关键点，龙珠x被移动的次数
    return fm[x];
}

void mmerge(int x, int y)
{
    int fx = mfind(x);
    int fy = mfind(y);
    if(fx != fy)
    {
        fm[fx] = fy;
        sum[fy] += sum[fx];             //计算龙珠fy处的龙珠总和
        mv[fx] = 1;                     //根节点首次被移动，所以移动次数为1
    }
}

void work()
{
    while(m--)
    {
        scanf("%s", s);
        if(s[0] == 'Q')
        {
            scanf("%d", &a);
            int fa = mfind(a);
            printf("%d %d %d
", fa, sum[fa], mv[a]);
        }
        else if(s[0] == 'T')
        {
            scanf("%d%d", &a, &b);
            mmerge(a, b);
        }
    }
}

int main()
{
    //freopen("test.in", "r", stdin);
    while(~scanf("%d", &t))
    {
        for(int tm = 1; tm <= t; tm++)
        {
            init();
            printf("Case %d:
", tm);
            work();
        }
    }
}