POJ-1988-Cube Stacking

题目传送门

零、经验总结

• 家族人数
• 到根节点距离
• 利用人数更新到根节点距离

一、题目大意

有\(n\)个箱子，初始时每个箱子单独为一列；

接下来有\(p\)行输入，\(M\), \(x\), \(y\) 或者 \(C\), \(x\)；

对于\(M\),\(x\),\(y\)：表示将\(x\)箱子所在的一列箱子搬到\(y\)所在的一列箱子上；

对于\(C\),\(x\)：表示查询箱子\(x\)下面有多少个箱子；

二、解析

本题在并查集的基础上，要求输出当前节点的子节点数量。
其实可以转化为带权并查集的问题，求出当前节点的祖先的总子孙数量，减去当前节点到祖先的距离再减一即可。

\(Up[x]\)代表\(x\)到自己的祖先的距离（也就是上面有多少节点）

\(sums[x]\)代表以\(x\)为根节点的子孙数量（只对根节点有效，因为在合并时，非根节点的\(sums\)值将不再被更新）

\(s[x]\)代表\(x\)的祖先

三、实现代码

// #include 
#include 
#include 

using namespace std;
const int N = 30010;
int P;      //操作数量
int fa[N];  //并查集数组
int son[N]; //每个家族中节点数量
int d[N];   //每个节点到根节点的距离
char op;    //操作符

//带权并查集模板
int find(int x) {
    //点权的理解：每个点到根的距离
    if (fa[x] == x) return x; //自己是老大，返回自己
    int root = find(fa[x]);   //通过自己父亲找老大
    d[x] += d[fa[x]];         //点权在路径压缩过程中，需要加上父亲的点权
    return fa[x] = root;      //路径压缩
}

//合并并查集
void join(int x, int y) {
    int px = find(x), py = find(y);
    if (px != py) {
        fa[py] = px; // px所在的子树放到py所在子树之上

        //下面这句话是本题相关的修改，重要！！！
        d[py] = son[px]; // py到px的距离就是px所在子树的结点个数[这个转换太漂亮了]

        son[px] += son[py]; // px所在子树结点个数要加上py这一棵树子树
    }
}

int main() {
    // fa父结点 son当前节点子树大小 dis当前节点到根结点距离
    for (int i = 1; i <= N - 10; i++) fa[i] = i, son[i] = 1;
    cin >> P;
    while (P--) {
        cin >> op;
        int x, y;
        if (op == 'M') { //合并
            cin >> x >> y;
            join(x, y);
        } else {
            cin >> x;
            //查找某一个点x下边有几个点时，只用求出x根结点所在子树的结点个数-x到根结点的距离-1
            printf("%d\n", son[find(x)] - d[x] - 1);
        }
    }
    return 0;
}